自动搬运

查看原文

来自洛谷，原作者为

	dingcx 不如回头再看一眼题面

搬运于2025-08-24 21:27:33，当前版本为作者最后更新于2019-12-05 22:45:53，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

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

思路

首先分析题目

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

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