#P1652. 圆

题目描述

给出 nn 个圆,保证任意两个圆都不相交且不相切。

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

输入格式

  • 第一行为一个整数 nn,表示圆的个数;
  • 第二行是 nn 个整数,表示 nn 个圆的 xx 坐标;
  • 第三行是 nn 个整数,表示 nn 个圆的 yy 坐标;
  • 第四行是 nn 个整数,表示 nn 个圆的半径 rr
  • 第五行是四个整数 x1,y1,x2,y2x_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%100\% 的数据,1n501\le n \le 50x,y1000|x|,|y| \le 10001r10001 \le r \le 1000

保证圆之间没有公共点。