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