明明明明子丶 @ 2019-10-04 20:03:49
窝觉得跟分治题解写的一模一样哇
#include<bits/stdc++.h>
using namespace std;
const int N=200005;
struct Node{
double x,y;
}a[N],t[N];
bool cmpx(const Node &a,const Node &b){
if(fabs(a.x-b.x)<=1e-5)
return a.y<b.y;
return a.x<b.x;
}
bool cmpy(const Node &a,const Node &b){
if(fabs(a.y-b.y)<=1e-5)
return a.x<b.x;
return a.y<b.y;
}
double ans=1e30;
double dis(int x,int y){
return (t[x].x-t[y].x)*(t[x].x-t[y].x)+(t[x].y-t[y].y)*(t[x].y-t[y].y);
}
double dis2(int x,int y){
return (a[x].x-a[y].x)*(a[x].x-a[y].x)+(a[x].y-a[y].y)*(a[x].y-a[y].y);
}
int tot;
void fz(int l,int r){
if(l>=r)return;
int m=(l+r)>>1;
fz(l,m);
fz(m+1,r);
double mx=a[m].x;
tot=0;
//t[tot]=a[m];
for(int i=l;i<=r;i++)
if(fabs(mx-a[i].x)<=ans+1e-5) t[++tot]=a[i];
sort(t+1,t+tot+1,cmpy);
for(int i=1;i<tot;i++)
for(int j=i+1;j<=tot&&t[j].y-t[i].y<=ans;j++)
ans=min(ans,dis(i,j));
}
int main(){
int n;
cin>>n;
for(int i=1;i<=n;i++)
scanf("%lf%lf",&a[i].x,&a[i].y);
sort(a+1,a+n+1,cmpx);
fz(1,n);
printf("%.4lf\n",sqrt(ans));
return 0;
}
by lc_lca @ 2019-10-04 20:23:08
重构代码/滑稽
by xwmwr @ 2019-10-05 16:00:59
吐槽一下,为啥会有double dis2(int x,int y)这个函数?