【Codeforces–1270E】Divide Points

题意#

给你 $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.$$

若旋转 $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{x-y}{2}\\ y^\prime=\frac{x+y}{2} \end{aligned} \right.$$

这样进行若干次，最终一定会使黑白点均存在。

分为了黑白点就可以由之前的方法解决，否则继续递归。

递归的次数为 $\mathcal O(\log A)$ 次，其中 $A$ 为坐标值域大小。