UOJ Logo Universal Online Judge

UOJ

附件下载 统计

为了让无法联网的跳蚤也能使用“跳找”发现新世界,你计划推动“跳找”搜索引擎接入卫星通信。

跳蚤王国共拥有 $n$ 颗通信卫星,每颗卫星的覆盖区域都是一个三角形。

若卫星 $R$ 的覆盖区域严格包含点 $p$,则称 $p$ 能连接 $R$,称点 $p$ 能连接的卫星集合为 $T_p$。

现在跳蚤国打算建立两处基站,设为点 $p_1,p_2$。若其满足 $T_{p_1} \cup T_{p_2}=S$,则能联系到到所有卫星,称这种建设方案为“完整的”。

第 $i$ 颗卫星的性能恰为第 $i$ ,称一个卫星集合 $T$ 中性能最好的的卫星为“主星”。

你要求出有哪些卫星可能在“完整的”基站建设方案中成为某个基站的“主星”,以方便咨询管理调度事宜。

即:对于每颗通信卫星 $S_i$,判定是否存在“完整的”基站建设方案 $p_1,p_2$,使得 $S_i$ 是 $T_{p_1}$ 或 $T_{p_2}$ 的“主星”。

输入格式

第一行一个整数 $n$,表示卫星的个数。

后 $n$ 行,每行六个整数 $x_1,y_1,x_2,y_2,x_3,y_3$。

描述一个顶点分别为 $(x_1,y_1),(x_2,y_2),(x_3,y_3)$ 的三角形,即为第 $i$ 个卫星的覆盖区域。

输出格式

输出一行长度为 $n$ 的 0/1 串,其中第 $i$ 个字符为 $1$ 表示第 $i$ 个卫星可能作为“主星”,反之为 $0$。

样例一

input

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

output

0111

explanation

可构成答案的两种“完整的”基站建设方案如图。

样例一

图中橙色点表示方案中包含的基站。紫色圈中的是“主星”。

样例二

input

5
1 1 1 6 2 1
1 1 1 5 3 1
1 1 1 4 4 1
1 1 1 3 5 1
1 1 1 2 6 1

output

11111

样例三

input

16
44 82 17 23 48 13 
21 26 31 53 73 46 
37 4 59 44 24 84 
4 27 10 91 76 3 
73 53 58 62 11 20 
7 11 94 8 13 94 
93 41 10 20 81 19 
4 42 52 92 52 33 
12 92 59 14 24 55 
37 6 95 68 1 43 
30 28 92 4 27 59 
26 7 82 34 15 23 
47 98 26 23 70 50 
5 100 3 8 95 65 
14 26 82 41 2 62 
82 31 7 30 55 65 

output

0000000000010101

限制与约定

对于所有数据,$1\leq n\leq 550,1\leq x_1,y_1,x_2,y_2,x_3,y_3\leq 10^5$ 且均为整数

子任务编号 $n\leq$ 分值
1 $16$ $20$
2 $50$ $25$
3 $160$ $15$
4 $550$ $40$

为了防止卡精度,保证将所有卫星覆盖区域的顶点任意移动不超过 $10^{-3}$ 单位后答案不变。

时间限制:$6\texttt{s}$

空间限制:$512\texttt{MB}$

下载

样例数据下载