Logo HelloWorld信息学奥赛题库

少儿编程

时间限制:1 s 空间限制:256 MB

#412. 魔法森林路径

统计

题目描述

在一片奇幻的魔法森林中,分布着 N 个神秘的魔法护盾区域。每个护盾区域都呈圆形,并且任意两个护盾区域都不相交且不相切。现在,有两位魔法师分别位于坐标为(x1, y1)和(x2, y2)的位置,且他们都不在任何一个护盾区域边界上。为了实现两位魔法师之间的魔法能量传输,需要构建一条连接他们位置的魔法路径。请问,这条魔法路径最少需要穿过多少次魔法护盾区域的边界?

输入格式:

第一行输入一个整数 N,表示魔法护盾区域的数量。
第二行包含 N 个整数,依次表示 N 个魔法护盾区域中心的 X 坐标。
第三行包含 N 个整数,依次表示 N 个魔法护盾区域中心的 Y 坐标。
第四行包含 N 个整数,依次表示 N 个魔法护盾区域的半径 R。
第五行包含四个整数 x1, y1, x2, y2,分别表示两位魔法师的位置坐标。

输出格式:

输出一个整数,代表魔法路径最少需要穿过魔法护盾区域边界的次数。

输入样例#1:

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

输出样例#1:

3

说明:

对于 100% 的数据,∣x∣,∣y∣≤1000,1≤r≤1000,1≤N≤1000。
保证圆形护盾区域之间没有公共点。