分治法的典例
当练手了
奇妙的是。使用inplace_merge按说应该是O(n)的算法。可是用sort nlogn的算法反而更快
先上快排版
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <cmath> using namespace std; const int SIZE = 10000+10;
const double INF = 100000; struct Point
{
double x,y;
}p[SIZE],q[SIZE]; int n; inline double dis(const Point a, const Point b)
{
return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
} bool cmpx(const Point &a, const Point &b)
{
return a.x<b.x;
} bool cmpy(const Point &a, const Point &b)
{
return a.y<b.y;
} double MinDis(int l,int r)
{
if(r-l<1)return INF;
if(r-l==1)return dis(p[r],p[l]); int m=(l+r)/2;
double d=min(MinDis(l,m),MinDis(m+1,r));
int left=l,right=r+1;
int i;
for(i=m;i>=l;i--)
if(p[i].x<p[m].x-d)
{
left=i+1;
break;
}
for(i=m;i<=r;i++)
if(p[i].x>p[m].x+d)
{
right=i;
break;
}
for(int i=left;i<right;i++)q[i]=p[i];
sort(q+left,q+right,cmpy);
int j;
double ret=d;
for(int i=left;i<right;i++)
{
for(j=i+1;j<right && q[j].y-q[i].y<d;j++)
{
ret=min(ret,dis(q[i],q[j]));
}
}
return ret; } int main()
{
double ans; while(scanf("%d",&n)&&n)
{
for(int i=0;i<n;i++)
{
scanf("%lf%lf",&p[i].x,&p[i].y);
}
sort(p,p+n,cmpx);
ans=MinDis(0,n-1);
if(ans>10000)printf("INFINITY\n");
else printf("%.4lf\n",ans);
} return 0;
}
再上归并
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <cmath> using namespace std; const int SIZE = 10000+10;
const double INF = 100000;
#define dis(a,b) sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y))
#define Fabs(x) x>0?x:-x
const double eps=1e-9; struct Point
{
double x,y;
}p[SIZE],q[SIZE]; int n; /*inline double dis(const Point a, const Point b)
{
return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}*/ bool cmpx(const Point &a, const Point &b)
{
return a.x<b.x;
} bool cmpy(const Point &a, const Point &b)
{
return a.y<b.y;
} double MinDis(int l,int r)
{
if(r-l<1)return INF;
//if(r-l==1)return dis(p[r],p[l]); int m=(l+r)/2;
double d=min(MinDis(l,m),MinDis(m+1,r));
inplace_merge(p+l,p+m+1,p+r+1,cmpy);
int j,right=0;
for(int i=l;i<=r;i++)//0 <n
if(p[i].x >= p[m].x-d && p[i].x<=p[m].x+d)
q[right++]=p[i];
double ret=INF;
for(int i=0;i<right;i++)
{
for(j=i+1;j<right && q[j].y-q[i].y<d;j++)
{
ret=min(ret,dis(q[i],q[j]));
}
}
return min(d,ret);
} int main()
{
double ans; while(scanf("%d",&n)&&n)
{
for(int i=0;i<n;i++)
{
scanf("%lf%lf",&p[i].x,&p[i].y);
}
sort(p,p+n,cmpx);
ans=MinDis(0,n-1);
if(ans>=10000)printf("INFINITY\n");
else printf("%.4lf\n",ans);
} return 0;
}