有木有能帮忙的人啊
查看原帖
有木有能帮忙的人啊
233972
秋水1024楼主2021/7/26 20:37
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<cmath>
#define ll long long
using namespace std;
int n,s[100086],tot;
struct node{
	double x,y;
}e[200021];
bool cmp(node a,node b){
	if(a.x==b.x)return a.y<b.y;
	return a.x<b.x;
}
bool cmp1(int a,int b){
	return e[a].y<e[b].y;
}
double jl(int a,int b){
	double jl0=(e[a].x-e[b].x)*(e[a].x-e[b].x)+(e[a].y-e[b].y)*(e[a].y-e[b].y);
	return sqrt(jl0);
}
double merge(int l,int r){
	if(l==r)return double(2<<20)+0.1;
	if(l==r-1)return jl(l,r);
	int mid=(l+r)/2;
	double d=min(merge(l,mid),merge(mid+1,r));
	memset(s,0,sizeof(s));s[1]=mid;tot=1;
	for(int i=l;i<=r;i++)
		if(abs(e[mid].x-e[i].x)<=d)
			s[++tot]=i;
	sort(s+1,s+tot+1,cmp1);
	for(int i=1;i<=tot;i++)
		for(int j=i+1;j<=tot&&abs(e[j].y-e[i].y)<=d;j++){
			double d0=jl(i,j);
			if(d>d0)d=d0;
		}
//	cout<<l<<" "<<r<<" "<<d<<endl;
	return d;
}
int main()
{
	scanf("%d", &n);
    for(int i=1; i<=n; i++)scanf("%lf%lf",&e[i].x,&e[i].y);
    //cout<<e[1].x<<e[1].y<<e[2].x<<e[2].y;
    sort(e,e+n+1, cmp);
    double ans=merge(1, n);
    printf("%.4lf\n",ans);
    return 0;
}
2021/7/26 20:37
加载中...