比赛 |
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;
}