Description

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?

Input Format

• 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 Format

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

7
1 -3 2 5 -4 12 12
1 -1 2 5 5 1 1
8 1 2 1 1 1 2
-5 1 12 1

3

Hint

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