比赛 4043级NOIP2022欢乐赛2nd 评测结果 AAAAAAAAAA
题目名称 平面最近点对 最终得分 100
用户昵称 ZRQ 运行时间 1.909 s
代码语言 C++ 内存使用 8.79 MiB
提交时间 2022-10-31 21:47:39
显示代码纯文本
//先恰个烂分写作业去了,回头补正解qwq 
#include<bits/stdc++.h>
using namespace std;
const int N=200005;
struct point
{
	double x,y;
}p[N];
double ran(){return (double)rand()/RAND_MAX;}
int n;
double ans=1e16;
double dis(point a,point b)
{
	return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);
}
inline bool cmp1(point a,point b)
{
	return a.x<b.x;
}
int main()
{
	freopen("closest.in","r",stdin);
	freopen("closest.out","w",stdout);
	srand(time(0));
	double a=ran()*acos(-1.0);
	cin>>n;
	for(int i=1;i<=n;++i)
	{
		double x,y;
		cin>>x>>y;
		p[i].x=x*cos(a)-y*sin(a),p[i].y=x*sin(a)+y*cos(a);
	}
	sort(p+1,p+1+n,cmp1);
	for(int i=1;i<=n;++i)
		for(int j=1;j<=50;++j)
			if(i+j<=n)
				ans=min(ans,dis(p[i],p[i+j]));
	printf("%.4lf\n",sqrt(ans));
	return 0;
}