Comet OJ

C1171 [Contest #7]毒瘤题

内存限制：256 MB 时间限制：2500 ms

题目描述

在平面直角坐标系中，

给 $n$ 个点，已知这 $n$ 个点是"可达的"，不保证这 $n$ 个点互不相同，并且如果点 $A$ 和点$B$ 都是"可达的"，则线段 $AB$ 上的点也都是"可达的"，可达的点仅由上述两条规则应用有限次得到。

给 $m$ 个圆，问有哪些圆满足圆内任意点都是可达的。

输入格式

第一行一个整数 $T$，表示数据组数

接下来 $T$ 组数据，每组数据中：

第一行一个整数 $n$，

接下来 $n$ 行每行两个整数 $x_i, y_i$，表示给定的$n$个可达的点，

接下来一行一个整数 $m$，

接下来 $m$ 行每行三个整数 $X_i, Y_i, R_i$，表示圆，其中 $(X_i , Y_i)$, $R_i$分别表示第 $i$个圆心座标以及半径。

数据范围：

$1 \le n,m \le 5 \times 10^5$

$1 \le R_i \le 10^6$

$-10^6 \le x_i,y_i,X_i,Y_i \le 10^6$

$\Sigma n \le 5 \times 10^5$

$\Sigma m \le 5 \times 10^5$

保证将 $R_i$ 改为 $R_i-1$ 或 $R_i+1$ 时，答案不发生变化。

输出

每组数据输出一行，该行包含一个长度为$m$ 的 $01$ 串，表示答案（第 $i$个字符是$0$ 表示第 $i$个内存在"不可达"的点，是 $1$ 則表示圆内所有点可达）。

样例

样例输入 1

1
8
1 10
1 -10
10 1
8 -5
-10 0
8 6
-4 8
-6 8
15
2 -1 3
8 -1 6
-7 -10 2
-10 -1 4
7 10 10
-1 -7 9
-5 0 5
-5 5 4
10 -7 4
-5 5 1
2 1 6
10 3 7
-2 0 3
-2 0 7
-9 -6 6

样例输出 1

100000000110100

提示

样例解释：

红色的点为样例中给出的点，橙色的⚪表示答案为 $1$ 的询问，蓝色的⚪表示答案为 $0$ 的询问。

E_sample.png