Sol1
神奇的构造。。
思路自然直接：枚举 \(Dist\) ，对所有 \(dist(i,j)=Dist\) 的点对连接 \(i,j\)，然后剔除所有度数为 \(0\) 的点，这样就建立了一张图。然后跑 dfs 判断是否是二分图：
① 若不是二分图，那当然所有点都得在一个集合中，用 dsu（并查集）表示关系。
② 若是二分图，那么一定可以奇偶染色。有两种选择，可以按颜色分成两个集合；可以全部归为一个集合。
那么怎么抉择呢？？？
巧妙的地方来了：对于 ② 可以发现无论怎么选择，一定得满足同种颜色的在同一集合中，那么先用 dsu 表示这种关系。然后遍历所有二分图，判断在处理之前的二分图之后，当前图是否还是二分图，是的话就强制分颜色，不是就归为一个集合。
首先还是二分图的话正确性显然。那什么时候可能出错呢？那就是 \(\exists a,b,c,d\)，同时 \(col[a]=col[b]=0,col[c]=col[d]=1\)，且在之前某张图合并了 \(a,c\)，且另一张图时分开了 \(b,d\)。但这是不可能的。因为一开始就绑定了 \(a,b\)，绑定了 \(c,d\)，那么 \(a->c,b->d\) 之间的关系一定是一样的，所以矛盾。
（更顶级的理解是在处理完非二分图和绑定二分图中同颜色点后，把被绑定的点集缩成一个点，每个二分图相当于缩点后的一条边，然后对缩点后的图跑二分图，能分开的就分开（这样才能保证两个集合），不能分开的就合并。）
所以这道题精髓在于先固定所有强制关系，然后用二分图判断非强制关系。
时间复杂度 \(O(n^2logn)\)
Sol2
好吧，题解给出了一个巧妙的构造。在此默写一遍
老样子，两个集合，那么就按坐标奇偶分类 \(A_{00},A_{01},A_{10},A_{11}\)
突然发现，若是只有一个集合，那么可以对平移坐标系，把横纵坐标都变成偶数，那么把坐标/2，方案一模一样。
然后假如有大于等于三个集合，那么按照 \(A_{00},A_{11}\) 一组，\(A_{01},A{1,0}\) 一组。这样组间距离是奇数，组内是偶数，显然成立。
最后只有两个集合，那么因为：
Notice: \(odd^2+odd^2=2 \mod 4,even^2+even^2=0\mod 4\)
所以直接分组，组间必然有一个坐标差是奇数，组内必然差值都是偶数，显然不等。
（什么小学奥数构造题。。。大学生完全不会
时间复杂度 \(O(n)\)。
Sol3
cf 上看到一个顶级构造，但实在是不明白证明，插个眼，之后来看（应该没时间的）。。。
原文地址：http://www.cnblogs.com/Huster-ZHY/p/16846390.html
