自动搬运

查看原文

来自洛谷，原作者为

	da32s1da **

搬运于2025-08-24 21:23:00，当前版本为作者最后更新于2018-07-17 07:38:31，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

@3A17K巨佬的神仙操作！

我们充分发扬人类智慧：

将所有点全部绕原点旋转同一个角度，然后按 x 坐标排序

根据数学直觉，在随机旋转后，答案中的两个点在数组中肯定不会离得太远

所以我们只取每个点向后的5个点来计算答案

这样速度快得飞起，在 n=1000000 时都可以在1s内卡过

注意旋转θ角时坐标变换

• x'=xcosθ-ysinθ
• y'=xsinθ+ycosθ

代码如下：

#include<cstdio>
#include<cmath>
#include<iostream>
#include<algorithm>
using namespace std;
const int N=2e5+50;
#define D double
struct spot{
	D a[4];
}p[N];
D x,y,x_,y_,z,w,ans;
int n;
bool mmp(const spot &u,const spot &v){
	return u.a[0]<v.a[0];
}
int main(){
	scanf("%d",&n);
	z=sin(1),w=cos(1);  //旋转1弧度≈57°
	for(int i=1;i<=n;i++){
		scanf("%lf%lf",&x,&y);
		x_=x*w-y*z;
		y_=x*z+y*w;   //计算旋转后的坐标
		p[i].a[0]=x_;
		p[i].a[1]=y_;
		p[i].a[2]=x;
		p[i].a[3]=y;   //存下来
	}
	sort(p+1,p+n+1,mmp);   //排序
	for(int i=n+1;i<=n+10;i++)
	p[i].a[0]=p[i].a[1]=-N-0.01;  //边界处理
	ans=2e9+0.01;  //初始化答案
	for(int i=1;i<=n;i++)
	for(int j=1;j<=5;j++){  //枚举
		x=p[i].a[2];y=p[i].a[3];
		x_=p[i+j].a[2];y_=p[i+j].a[3];
		z=sqrt((x-x_)*(x-x_)+(y-y_)*(y-y_));  //计算距离
		if(ans>z)ans=z;   //更新答案
	}
	printf("%.4lf\n",ans);  //输出
}
/*
x'=xcosθ-ysinθ
y'=xsinθ+ycosθ
*/

人类的智慧是无穷无尽的！