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

「ROI 2025 Day2」沼泽里的青蛙

题目描述

译自 ROI 2025 Day2 T2. Лягушки на болоте

在索契筹备 2014 年奥运会时,意外引入了来自远东的小型蝴蝶——箱树蛾。它毁掉了当地的箱树林,迫使树蛙们搬到了沼泽里生活。不过,这些聪明的树蛙依然保留了它们的神奇本领:每次跳跃后,它们的颜色会在绿色和棕色之间切换。

沼泽是一片平面,上面散布着许多小土丘,可以看作平面上的点。青蛙一次跳跃可以从当前土丘跳到任何一个距离不超过 rr 的其他土丘。跳跃后,青蛙的颜色会变成相反的颜色。需要注意的是,青蛙无法在原地跳跃。

你的任务是,对于从 11nn 的每个起始土丘,判断青蛙能否通过若干次跳跃回到这个土丘,并且在回到时颜色与初始时相反。

输入格式

第一行包含两个整数 nnrr (2n105,1r109)(2 \le n \le 10^5, 1 \le r \le 10^9),分别表示沼泽中土丘的数量和青蛙的最大跳跃距离。

接下来的 nn 行,每行包含两个整数 xix_iyiy_i (0xi,yi5108)(0 \le x_i, y_i \le 5 \cdot 10^8),表示第 ii 个土丘的坐标。

保证任意两个土丘的坐标不重合。

输出格式

输出一个长度为 nn 的字符串,包含字符 01。如果从第 ii 个土丘开始的青蛙能回到该土丘且颜色相反,则第 ii 个字符为 1;否则为 0

6 5
4 1
4 4
1 5
5 9
9 6
10 2

111000

提示

样例解释

下图展示了从第一个土丘开始,青蛙通过跳跃改变颜色的路径:


详细子任务附加限制及分值如下表所示。其中子任务 00 是样例。

子任务 分值 附加限制
00 样例
11 1010 n3n \le 3
22 2020 n200n \le 200
33 66 n1000n \le 1\,000
44 99 n10000n \le 10\,000
55 1616 yi=0y_i = 0
66 55 r2r \le 2
77 r4r \le 4
88 r10r \le 10
99 1212 (xixj)2+(yiyj)2r24(x_i - x_j)^2 + (y_i - y_j)^2 \ge \frac{r^2}{4}iji \ne j
1010 无附加限制