题目连接:hdu_1007_Quoit Design

题意:

给你平面上的一些点,让你找出这些点的最近点对的距离

题解:
采用分治,达到O(nlognlogn)的时间复杂度就能艹过去了

 #include<stdio.h>
#include<string.h>
#include<algorithm>
#include<math.h>
using namespace std;
//O(nlognlogn)找最近点对
const int N=1e5+;
struct TPoint
{
double x,y;
}ply[N],ans[N];
int n;
inline double MIN(double a,double b) {return a<b?a:b;}
bool cmpx(TPoint a,TPoint b) {return a.x<b.x;}
bool cmpy(TPoint a,TPoint b) {return a.y<b.y;}
double dist(TPoint a,TPoint b)
{
double s1=a.x-b.x;
double t1=a.y-b.y;
return sqrt(s1*s1+t1*t1);
}
double closest(int l,int r)
{
if(l+==r) return dist(ply[l],ply[r]);//2点
else if(l+==r)//三点
return MIN(dist(ply[l],ply[l+]),MIN(dist(ply[l],ply[r]),dist(ply[l+],ply[r])));
int i,j,mid,cnt;
mid=(l+r)>>;
double mi=MIN(closest(l,mid),closest(mid+,r));//递归解决
for(i=l,cnt=;i<=r;i++)//相邻点符合
{
if(fabs(ply[i].x-ply[mid].x)<=mi)
ans[cnt++]=ply[i];
}
sort(ans,ans+cnt,cmpy);//按y排序
for(i=;i<cnt;i++)for(j=i+;j<cnt;j++)//更新最小距离
{
if(ans[j].y-ans[i].y>=mi) break;
mi=MIN(mi,dist(ans[i],ans[j]));
}
return mi;
}
int main()
{
while(scanf("%d",&n),n)
{
int i;
for(i=;i<n;i++) scanf("%lf%lf",&ply[i].x,&ply[i].y);//输入点
sort(ply,ply+n,cmpx);//按x排序
double mi=closest(,n-);
printf("%.2lf\n",mi/);
}
return ;
}
05-06 16:17