4730: 正方形扩展(广东省重点中学信息学邀请赛普及组)
内存限制：512 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：0
解决：0
题目描述
（广东省重点中学信息学邀请赛 (GDKOI 2024 day2普及组 第二试)
现在，在笛卡尔坐标系（无限大二维平面）上有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个种类互不相同的细菌，它们所在的坐标也互不相同。随着时间的增加，细菌们不断繁殖，以正方形的形状、用相同的正方形扩张速度，同时扩张自己的领地。
具体来说对于任意时刻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≤n≤106)表示细菌母体的数量。
接下来输入n行，每行输入两个整数，表示点的坐标(xi, yi)，即种类为i的细菌母体的位置。
接下来输入n行，每行输入两个整数，表示点的坐标(xi, yi)，即种类为i的细菌母体的位置。
输出
输出一个长度为n的01串，对于其中第i个数字，1表示种类为i的细菌的占领面积可以扩张到无穷大，0则表示最终面积有限。
样例输入 复制
5
0 0
2 0
2 2
0 2
1 1样例输出 复制
11110提示
数据范围：
对于25%数据,n≤102。
对于50%数据,n≤103。
对于75%数据,n≤105。
对于100%数据,n≤106,−109≤xi,yi≤109。
对于25%数据,n≤102。
对于50%数据,n≤103。
对于75%数据,n≤105。
对于100%数据,n≤106,−109≤xi,yi≤109。