题目描述

给出 $n$ 个圆，保证任意两个圆都不相交且不相切。

然后给出两个点 $(x_1,y_1),(x_2,y_2)$，保证均不在某个圆上。现在要从 $(x_1,y_1) \to (x_2,y_2)$ 画条曲线，问这条曲线最少穿过多少次圆的边界？

输入格式

• 第一行为一个整数 $n$，表示圆的个数；
• 第二行是 $n$ 个整数，表示 $n$ 个圆的 $x$ 坐标；
• 第三行是 $n$ 个整数，表示 $n$ 个圆的 $y$ 坐标；
• 第四行是 $n$ 个整数，表示 $n$ 个圆的半径 $r$；
• 第五行是四个整数 $x_1,y_1,x_2,y_2$。

输出格式

仅一个整数，表示最少要穿过多少次圆的边界。

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

提示

【数据范围】

对于 $100\%$ 的数据，$1\le n \le 50$，$|x|,|y| \le 1000$，$1 \le r \le 1000$。

保证圆之间没有公共点。