题解 P1652 【圆】

· · 题解

要清楚，这道题是红题！（不要想复杂了）

思路

首先分析题目

1.相离的意思可不是外离，内含也算相离。（我开始也理解错了，看了讨论才知道，我可没看题解）

2.要画一条曲线，意思就是想怎么弯就怎么弯。所以最终要求的就是两个点的连线最少穿过几个圆。

怎么求

例如这样

这里三个圆都把两点分隔在了两边，所以是3。随便连一条线就行了，可以：

或者这样

有一个圆没有用，另外两个圆都起到了分隔作用，所以是2。可以这样连：

还可以是这样

外面的圆把里面的所有东西都套住了，同样没有用，而其余两个圆都有用，所以也是2。可以这样：

很容易总结出答案就是把所有把两个点分隔的圆的个数，也就是其中一个在圆内，另一个在圆外的圆的个数。

细节

距离就是\sqrt{(x1-x2)^2+(y1-y2)^2}

注意y1不能设为全局变量（局部变量可以），会出bug。

判断一个在圆内，另一个在圆外时，可以用异或，看两点到圆心的距离是否小于（不能等于）半径。

代码

相信没有多少人喜欢上面的一通分析吧，那么，你们喜欢的代码来了——

代码长度19行（很短），时间3ms（挺快）

#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;//华丽结束
}

看我这么辛苦画了这么多图，作了这么多分析，总得点个赞再走呀！