给出 n 个圆,保证任意两个圆都不相交且不相切。
然后给出两个点 (x1,y1),(x2,y2),保证均不在某个圆上。现在要从 (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% 的数据,1≤n≤50,∣x∣,∣y∣≤1000,1≤r≤1000。
保证圆之间没有公共点。
//核心思路:对于任意一个圆,只要一个在圆内,一个在圆外,则结果加1
#include<cstdio>
#include<cmath>//用到sqrt,即开根
using namespace std;
int x[60],y[60],r[60];//读入的三个数组
double dist(int x1,int y1,int x2,int y2){//求距离的函数
return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));//公式
}
int main(){
int n,x1,y1,x2,y2,ans=0;
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",&x[i]);
for(int i=1;i<=n;i++) scanf("%d",&y[i]);
for(int i=1;i<=n;i++) scanf("%d",&r[i]);
scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
for(int i=1;i<=n;i++)//每个圆都搜一遍
if((dist(x1,y1,x[i],y[i])<r[i])^(dist(x2,y2,x[i],y[i]))<r[i]) ans++;//如果两个点恰有一个在圆内,就累加上
printf("%d",ans);//输出总和
return 0;//华丽结束
}
这里我最想说的就是代码中异或的作用,异或(XOR)是一种逻辑运算符,广泛应用于数学、计算机科学和电子电路设计中。它的基本思想是:当两个输入不同时,结果为真;当两个输入相同时,结果为假。真牛