[GDKOI2024 普及组] 正方形扩展

赛事要求

2024 年广东省重点中学信息学邀请赛 (GDKOI 2024)

普及组 第二试

2024 年 1 月 7 日

注意事项

1. 严格按照题目所要求的格式进行输入、输出，否则严重影响得分。
2. 题目测试数据有严格的时间限制，超时不得分。
3. C/C++ 中函数 main() 的返回值类型必须是 int，程序正常结束时的返回值必须是 0。
4. 输入文件格式不用判错；输入输出文件名均已给定，不用键盘输入。
5. 评测环境为 NOI 系列活动标准竞赛环境，编译器版本为 g++ 9.4.0。
6. 若无特殊说明，结果的比较方式为全文比较 (过滤行末空格及文末回车)。
7. 对于 C++ 选手，64 位整数输入输出格式为 %lld。
8. 选手提交的程序源文件必须不大于 100KB。
9. 对于 C++ 语言的编译选项为 -O2 -std=c++14

题目描述

现在，在笛卡尔坐标系（无限大二维平面）上有 $n$ 个种类互不相同的细菌，它们所在的坐标也互不相同。

随着时间的增加，细菌们不断繁殖，以正方形的形状、用相同的正方形扩张速度，同时扩张自己的领地。

具体来说对于任意时刻 $t$、平面上任意一点 $p$，假设该点 $p$ 上存在第 $i$ 种细菌，那么有以下两种情况：

• 如果以点 $p$ 为中心的任意正方形都含有其他种类的细菌，则该点的细菌将不会扩张（可以称之为“接触抑制”）。
• 如果存在一个以 $p$ 为中心的正方形不含有其他种类的细菌，则该点的细菌将会进行扩张。

注意，扩展出去的同种细菌也具备一样的扩展能力。

以下是一些简单的关于正方形扩展的例子：

若初始时，平面只有唯一的一个细菌位于 $(0, 0)$，那么过一个单位时间后，这一类细菌将占领 $(1, 1) (1, -1) (-1, -1) (-1, 1)$ 围成的正方形。

若初始时，平面有两个细菌分别位于 $(0, 0)$ 和 $(1, 0)$，那么最终 $(0.5, 0)$ 会成为他们领地的分界线，一开始位于 $(0, 0)$ 的细菌会占领 $(0.5, 0)$ 左侧的全部区域，位于 $(1, 0)$ 的细菌会占领 $(0.5, 0)$ 右侧的全部区域。

现在询问对于第 $i$ 种细菌，询问其占领面积能否趋于无穷大。

输入格式

第一行一个正整数 $n(1 \leq n \leq 10^6)$ 表示细菌母体的数量。

接下来输入 $n$ 行，每行输入两个整数，表示点的坐标 $(x_i, y_i)$，即种类为 $i$ 的细菌母体的位置。

输出格式

输出一个长度为 $n$ 的 $01$ 串，对于其中第 $i$ 个数字，$1$ 表示种类为 $i$ 的细菌的占领面积可以扩张到无穷大，$0$ 则表示最终面积有限。

样例 #1

样例输入 #1

5
0 0
2 0
2 2
0 2
1 1

样例输出 #1

11110

样例 #2

样例输入 #2

3
-2 0
0 0
2 0

样例输出 #2

111

样例 #3

样例输入 #3

7
-7 -8
5 -9
1 -5
9 -4
-8 3
-2 -3
-4 -6

样例输出 #3

1101110

提示

【样例解释】

在第二个样例，点 $(0, 0)$ 最终拥有的领地是直线 $x = -1$ 与 $x = 1$ 夹的中间部分，面积趋于无穷大。

【数据范围】

对于 $25\%$ 数据，$n \leq 10^2$。

对于 $50\%$ 数据，$n \leq 10^3$。

对于 $75\%$ 数据，$n \leq 10^5$。

对于 $100\%$ 数据，$1\leq n \leq 10^6$，$-10^9 \leq x_i, y_i \leq 10^9$。