游耕者（夜）题解¶
解法比较¶
出题人解法做四次坐标变换与方向扫描：按横坐标排序，在以 \(y-x\) 为索引的树状数组中维护最小 \(x+y\) ，为每个点找所在扇区的候选近邻；重合点用零权边连接，再用 Kruskal 求曼哈顿最小生成树。递归 DFS 按首次访问顺序形成巡回。候选边交换论证和加倍树边后取捷径的证明均沿用出题人解法，见下文。
出题人实现把有界坐标平移后直接作为树状数组下标。Codex（GPT-6）采用的实现压缩实际出现的坐标，统一重合点处理，并用显式栈遍历。若直接坐标下标范围为 \(U\) ，直接索引的时间为 \(O(n\log(n+1)+n\log(U+1)+U)\) 、空间为 \(O(n+U)\) ；Codex 实现为 \(O(n\log(n+1))\) 时间、\(O(n)\) 空间。优势是工作区不依赖坐标跨度，并避免深递归；方向筛边与巡回构造的证明适用于两种坐标表示。
从最小生成树构造巡回路线¶
把农场作为顶点，两点之间的距离作为无向边权。题面定义的最小连接成本 \(M\) 正是这个完全图的最小生成树权值：任何连通图都能删除环上的边，得到权值不增的生成树。
求出一棵最小生成树 \(T\) ，以农场 \(1\) 为根做深度优先遍历，只在首次到达顶点时将它加入序列，最后补上 \(1\) .实际实现使用显式栈，避免长链上的递归栈溢出。
为什么总代价不超过两倍¶
沿树边往返的完整遍历把每条边走两次，总代价恰为 \(2M\) .从这个行走序列中跳过已经访问过的顶点，保留首次访问顺序和最终返回起点。由三角不等式，用一条直达边替换一段路径不会增加代价，所以得到的巡回路线满足：
图中左侧树的完整往返顺序为 \(1,2,3,4,3,2,1\) ，代价为 \(60\) .跳过重复访问后得到右侧的 \(1,2,3,4,1\) ，代价为 \(40\) .
若最优巡回长度为 \(OPT\) ，从最优回路中删去一条边便得到生成树，因此 \(M\le OPT\) .参考构造满足 \(C\le2OPT\) .题面为评测保留的容差允许 \(C\le2.001M+0.001\) ，因此不能把所有获接受路线都宣称为严格的 2 倍近似。
重合点和边界¶
按坐标排序，将同坐标的农场保留一个代表，其余编号用零权边连接到代表。仅对互不相同的坐标求树，再加入这些零权边。它们不改变 \(M\) ，并保证每个原始编号都出现在最终巡回中。
单个农场输出 1 1 ；全部农场重合时 \(M=C=0\) .不假设点处于一般位置，也不以随机扰动改变坐标或边权。
曼哈顿距离与三角不等式¶
横、纵坐标的绝对差分别满足三角不等式，将两式相加便得到 \(d(a,c)\le d(a,b)+d(b,c)\) .因此前述跳过重复访问的构造适用。
用方向扫描求曼哈顿最小生成树¶
不能显式建立完全图。曼哈顿 MST 的方向筛边性质允许对每个点只保留各个 \(45^\circ\) 区域中的一个最近邻，由这些线性数量的边求出一棵 MST。同一区域中两点之间的距离不会大于它们到区域顶点的较大距离，因此可通过树边交换排除不必要的远邻。并列距离可选择确定的最近邻；实现也覆盖区域边界。
边是无向的，只需覆盖朝向右半平面的四个区域。考虑其中满足下式的区域：
这也保证 \(y_j\ge y_i\) ，因此两点之间的距离为：
固定 \(i\) 后，只需在满足上述条件的点中找 \(x_j+y_j\) 最小的点。
- 按横坐标降序、纵坐标降序扫描，已经处理的点满足横坐标条件；同横坐标的点按纵坐标降序处理。
- 将所有 \(y-x\) 离散化并反向编号。用树状数组维护每个前缀中 \(x+y\) 最小的点；相等时按原编号确定顺序。
- 查询当前 \(y_i-x_i\) 对应的后缀，得到最近邻并加入候选边，然后插入当前点。
- 对坐标变换 \((x,y)\) 、\((y,x)\) 、\((-y,x)\) 、\((x,-y)\) 分别做一次扫描，覆盖右上和右下的四个区域。无向边同时覆盖反方向。
- 对至多线性数量的候选边排序，使用 Kruskal，并合并重合农场之间的零权边。
离散化使树状数组大小只与不同坐标的数量有关，不依赖坐标值域。每轮排序、查询和插入均为 \(O(n\log n)\) ，四轮仍为 \(O(n\log n)\) .
整数与实现细节¶
方向扫描中的坐标变换保持曼哈顿距离不变。候选边的权值用变换后的坐标和之差计算，但端点一直保存原农场编号。
本题一条边的代价不超过 \(40000\) ，总路线长度以及评测中乘以 \(1000\) 或 \(2001\) 的结果使用有符号 64 位整数。所有距离和判定均为整数运算。
复杂度¶
设农场数为 \(n\) .去重、候选边生成及 Kruskal 共需 \(O(n\log(n+1))\) 时间，树遍历需 \(O(n)\) 时间；总空间为 \(O(n)\) .使用 \(\log(n+1)\) 兼顾单点情形。完整图 Prim 对照程序需 \(O(n^2)\) 时间和 \(O(n)\) 空间，仅用于小规模验证。
特殊评测与复现¶
由于 \(C,M\) 都是整数，精确使用以下等价条件：
评测器检查恰有 \(n+1\) 个整数、首尾为 \(1\) 、前 \(n\) 个编号组成排列，并逐边重算 \(C\) .随后从输入重新计算 \(M\) ，不读取参考路线的首个编号作为长度，也不把参考路线长度当作最优值。参考输出文件只为统一接口而要求存在，其内容不参与判定。
编译时保留题目目录内的 mst.hpp .标准程序与评测器共享这份经过独立对拍的实现；标准程序的输出只有巡回序列。
g++ -std=c++17 -O2 std.cpp -o std
g++ -std=c++17 -O2 tests/checker.cpp -o checker
g++ -std=c++17 -O2 brute.cpp -o brute
g++ -std=c++17 -O2 tests/mst_weight.cpp -o mst_weight
python tests/generate.py --out-dir ../../../build/data/nomadism-night --std ./std
checker input.in reference.out contestant.out
checker 的退出码为：0 通过、1 答案错误、2 调用或输入材料错误。完整重新计算 \(M\) 的开销属于检查器，部署时应为它设置足够的时间和内存。brute.cpp 是独立的完全图 Prim，只输出 \(M\) ；tests/mst_weight.cpp 是诊断工具，输出 \(M\) 及所选树的平方边长和，两者都支持连续读取多份输入到文件末尾。
正式数据使用固定 SplitMix64 种子，覆盖随机点、规则网格、窄条、等横坐标、共线、共圆、重合点、远隔点簇和最大规模。性能测量见 评测环境与性能。