题意
给你 $n$ 个整点和它们的坐标，现在给它们分成两组并两两连上边。
对于每条边，如果两端的点在：同一组则边为黄色，不同组则为蓝色。
现在让你给出任意一种分组方案，使得所有长度相同的边颜色相同。
保证存在合法方案。
$2\leq n\leq 10^3$，$|x_i|, |y_i|\leq 10^6$.
题解
将点分为黑色和白色两组。
考虑对格子黑白染色，坐标和为偶数的染为黑色。
一、若两种颜色的点都存在
黄色边的边长平方一定是奇数，蓝色边的边长平方一定是偶数，满足题目条件。
直接按黑白颜色分组即可。
二、若只存在一种颜色的点
不妨设只存在黑点，因为只有白点，就可以全部下移一格，转化为黑点。
如果所有点的两维坐标都是偶数，则可以直接 $\div 2$，但我们只保证了 $2\mid (x+y)$.
想要转化到让 $(x+y)$ 既有奇数又有偶数，过程中不改变点之间的位置关系。
注意到 $2\mid (x+y)\Rightarrow 2\mid (x-y)$.
联想到坐标旋转公式：
$$
\left\{
\begin{aligned}
x^\prime=x\cos \theta-y\sin \theta\\
y^\prime=x\sin \theta+y\cos \theta
\end{aligned}
\right.
$$
\left\{
\begin{aligned}
x^\prime=x\cos \theta-y\sin \theta\\
y^\prime=x\sin \theta+y\cos \theta
\end{aligned}
\right.
$$
若旋转 $45\degree$，则有：
$$
\left\{
\begin{aligned}
x^\prime=\frac{\sqrt{2}}{2}x-\frac{\sqrt{2}}{2}y=\frac{\sqrt{2}}{2}(x-y)\\
y^\prime=\frac{\sqrt{2}}{2}x+\frac{\sqrt{2}}{2}y=\frac{\sqrt{2}}{2}(x+y)
\end{aligned}
\right.
$$
\left\{
\begin{aligned}
x^\prime=\frac{\sqrt{2}}{2}x-\frac{\sqrt{2}}{2}y=\frac{\sqrt{2}}{2}(x-y)\\
y^\prime=\frac{\sqrt{2}}{2}x+\frac{\sqrt{2}}{2}y=\frac{\sqrt{2}}{2}(x+y)
\end{aligned}
\right.
$$
旋转和缩放都可以保证点间位置关系不变。我们只想看到整数，于是让：
$$
\left\{
\begin{aligned}
x^\prime=\frac{x-y}{2}\\
y^\prime=\frac{x+y}{2}
\end{aligned}
\right.
$$
\left\{
\begin{aligned}
x^\prime=\frac{x-y}{2}\\
y^\prime=\frac{x+y}{2}
\end{aligned}
\right.
$$
这样进行若干次，最终一定会使黑白点均存在。
分为了黑白点就可以由之前的方法解决，否则继续递归。
递归的次数为 $\mathcal O(\log A)$ 次，其中 $A$ 为坐标值域大小。