C1511 [Ynoi]2012-B

内存限制:256 MB 时间限制:3000 ms

题目描述

在平面直角坐标系中,给 $n$ 个点,这 $n$个点是可达的。

如果点 $A,B$ 可达则线段 $AB$ 上的点均可达。

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

输入格式

第一行一个整数 $T$,表示数据组数;接下来 $T$ 组数据,每组数据中:

第一行一个整数 $n$,接下来 $n$ 行每行两个整数 $x_i,y_i$,表示点,接下来一行一个整数 $m$,接下来 $m$ 行每行三个整数 $X_i,Y_i,R_i$,表示圆。

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

$1 \le R_i \le 1 \times 10^6$

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

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

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

保证当 $R_i$ 变化不超过 $1$ 时,答案不发生变化。

输出

每组数据输出一行,一个长度 $m$ 的01串,表示答案(0表示圆内存在不可达的点,1表示圆内所有点可达)

样例

样例输入 1

样例输出 1

提示