Problem Description

In the 2D Cartesian coordinate system,

You are given $n$ points. These $n$ points are reachable. If points $A, B$ are reachable, then all points on the segment $AB$ are also reachable.

You are given $m$ circles. Determine which circles satisfy that every point inside the circle is reachable.

Input Format

The first line contains an integer $T$, which indicates the number of test cases.

Then there are $T$ test cases. For each test case:

The first line contains an integer $n$.

The next $n$ lines each contain two integers $x_i, y_i$, representing a point.

The next line contains an integer $m$.

The next $m$ lines each contain three integers $X_i, Y_i, R_i$, representing a circle.

Output Format

For each test case, output one line: a 01 string of length $m$, representing the answers (0 means there exists an unreachable point inside the circle, 1 means all points inside the circle are reachable).

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

100000000110100

Hint

Idea: ccz181078, Solution: ccz181078, Code: ccz181078, Data: ccz181078.

Sample explanation:

The red points are the points given in the sample. The orange circles indicate queries with answer 1, and the blue circles indicate queries with answer 0.

Constraints: $1\leq n,m\leq 5\times 10^5$, $1\leq R_i\leq 10^6$, $-10^6\leq x_i,y_i,X_i,Y_i\leq 10^6$, $\sum n\leq 5\times 10^5$, $\sum m\leq 5\times 10^5$.

It is guaranteed that when $R_i$ changes by no more than $1$, the answer does not change.

Translated by ChatGPT 5