P2778 [AHOI2016 Middle School Division] Maze

Xiaoxue and Xiaokeke are trapped in an infinite maze. It is known that this maze has $N$ ring-shaped walls. If we regard the entire maze as a 2D plane, then each wall is a circle on the plane. Any two circles do not intersect, do not coincide, and are not tangent, but they may contain each other. Xiaoxue and Xiaokeke are trapped at two different positions, and it is guaranteed that their positions do not lie on any of these circles. They can pass through only by breaking the walls. Xiaoxue wants to know the minimum number of walls they need to break in order to meet. They may meet at any location.

The first line contains an integer $N$, the number of walls. The next $N$ lines each contain three integers $x, y, r$, indicating a ring-shaped wall that is a circle centered at $(x, y)$ with radius $r$. The next line contains an integer $Q$, the number of queries. The following $Q$ lines each contain four integers $a, b, c, d$, representing one query: Xiaoxue is at position $(a, b)$, and Xiaokeke is at position $(c, d)$.

Output $Q$ lines, one per query. For each query, output one integer: the minimum number of walls that must be broken for them to meet.

For $20\%$ of the testdata, $0\le N\le 200$. For $40\%$ of the testdata, $0\le N\le 1000$. For $100\%$ of the testdata, $0\le N, Q\le 8000,-10^8\le x,y,r, a, b, c, d\le 10^8$. In addition, there is an extra $20\%$ of the testdata with $0\le N\le 1000, 0\le Q\le 1000$. Large testdata time limit: $\rm 3\ s$. Translated by ChatGPT 5