比赛 |
4043级NOIP2022欢乐赛2nd |
评测结果 |
AAAAAAAAAA |
题目名称 |
平面最近点对 |
最终得分 |
100 |
用户昵称 |
op_组撒头屯 |
运行时间 |
0.938 s |
代码语言 |
C++ |
内存使用 |
11.84 MiB |
提交时间 |
2022-10-31 21:06:25 |
显示代码纯文本
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=200000+5;
const ll inf=0x3f3f3f3f3f3f;
struct sdf{
ll x,y;
}q[N],tmp[N];
int n;
ll ans=inf;
bool cmp(sdf a,sdf b){
if (a.x!=b.x)return a.x<b.x;
return a.y<b.y;
}
bool cmp2(sdf a,sdf b){
if (a.y!=b.y)return a.y>b.y;
return a.x<b.x;
}
inline ll abss(ll x){
return (x<0)?-x:x;
}
inline double dis(sdf a,sdf b){
return sqrt((a.y-b.y)*(a.y-b.y)+(a.x-b.x)*(a.x-b.x));
}
double cdq(int l,int r){
if (l==r)return 1e18;
int mid=(l+r)/2;
double mn1=cdq(l,mid),mn2=cdq(mid+1,r);
double mn=min(mn1,mn2);
ll midx=q[mid].x;int cnt=0;
for (int i=l;i<=r;i++){
if (abss(q[i].x-midx)<=mn)tmp[++cnt]=q[i];
}
sort(tmp+1,tmp+cnt+1,cmp2);
for (int i=1;i<=cnt;i++){
int j=i+1;
while(j<=cnt&&abss(tmp[i].y-tmp[j].y)<=mn)mn=min(mn,dis(tmp[i],tmp[j])),j++;
}
return mn;
}
int main(){
freopen ("closest.in","r",stdin);
freopen ("closest.out","w",stdout);
scanf("%d",&n);
for (int i=1;i<=n;i++){
scanf("%lld%lld",&q[i].x,&q[i].y);
}
sort(q+1,q+n+1,cmp);
printf("%.4lf\n",cdq(1,n));
return 0;
}