P1652 Circles

You are given $n$ circles, and it is guaranteed that any two circles do not intersect and are not tangent. You are then given two points $(x_1,y_1),(x_2,y_2)$, both guaranteed to be not on any circle. Now you want to draw a curve from $(x_1,y_1) \to (x_2,y_2)$. What is the minimum number of times this curve must cross the boundaries of the circles?

- The first line contains an integer $n$, the number of circles. - The second line contains $n$ integers, the $x$-coordinates of the circles. - The third line contains $n$ integers, the $y$-coordinates of the circles. - The fourth line contains $n$ integers, the radii $r$ of the circles. - The fifth line contains four integers $x_1,y_1,x_2,y_2$.

Output a single integer, the minimum number of times the curve must cross the boundaries of the circles.

Constraints For $100\%$ of the testdata, $1 \le n \le 50$, $|x|, |y| \le 1000$, $1 \le r \le 1000$. It is guaranteed that no two circles share any point. Translated by ChatGPT 5