P12506 「ROI 2025 Day2」沼泽里的青蛙

**译自 [ROI 2025](https://neerc.ifmo.ru/school/archive/2024-2025.html) Day2 T2.** ***[Лягушки на болоте](https://neerc.ifmo.ru/school/archive/2024-2025/ru-olymp-roi-2025-day2.pdf)*** 在索契筹备 2014 年奥运会时，意外引入了来自远东的小型蝴蝶——箱树蛾。它毁掉了当地的箱树林，迫使树蛙们搬到了沼泽里生活。不过，这些聪明的树蛙依然保留了它们的神奇本领：每次跳跃后，它们的颜色会在绿色和棕色之间切换。 沼泽是一片平面，上面散布着许多小土丘，可以看作平面上的点。青蛙一次跳跃可以从当前土丘跳到任何一个距离不超过 $r$ 的其他土丘。跳跃后，青蛙的颜色会变成相反的颜色。需要注意的是，青蛙无法在原地跳跃。 你的任务是，对于从 $1$ 到 $n$ 的每个起始土丘，判断青蛙能否通过若干次跳跃回到这个土丘，并且在回到时颜色与初始时相反。

第一行包含两个整数 $n$ 和 $r$ $(2 \le n \le 10^5, 1 \le r \le 10^9)$，分别表示沼泽中土丘的数量和青蛙的最大跳跃距离。 接下来的 $n$ 行，每行包含两个整数 $x_i$ 和 $y_i$ $(0 \le x_i, y_i \le 5 \cdot 10^8)$，表示第 $i$ 个土丘的坐标。 保证任意两个土丘的坐标不重合。

输出一个长度为 $n$ 的字符串，包含字符 `0` 或 `1`。如果从第 $i$ 个土丘开始的青蛙能回到该土丘且颜色相反，则第 $i$ 个字符为 `1`；否则为 `0`。

### 样例解释 下图展示了从第一个土丘开始，青蛙通过跳跃改变颜色的路径：  --- 详细子任务附加限制及分值如下表所示。其中子任务 $0$ 是样例。 | 子任务 | 分值 | 附加限制 | | :-: | :-: | :-: | |$0$|$0$|样例|| | $1$ | $10$ | $n \le 3$ | | | $2$ | $20$ | $n \le 200$ | $0,1$ | | $3$ | $6$ | $n \le 1\,000$ | $0,1,2$ | | $4$ | $9$ | $n \le 10\,000$ | $0,1-3$ | | $5$ | $16$ | $y_i = 0$ | | | $6$ | $5$ | $r \le 2$ | | | $7$ | $5$ | $r \le 4$ | $6$ | | $8$ | $5$ | $r \le 10$ | $0,6,7$ | | $9$ | $12$ | $(x_i - x_j)^2 + (y_i - y_j)^2 \ge \frac{r^2}{4}$，$i \ne j$ | $0,6$ | | $10$ | $12$ | 无附加限制 | $0,1-9$ |