给出 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 。
保证圆之间没有公共点。