题目地址：http://acm.hdu.edu.cn/showproblem.php?pid=1007
具体算法分析见：最接近点对问题
版本一：
#include <iostream>
#include<cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
using namespace std;
const int N = 100005;
const double MAX = 10e100;
const double eps = 0.00001;
typedef struct TYPE
{
double x, y;
int index;
} Point;
Point a[N], b[N], c[N];
double closest(Point *, Point *, Point *, int, int);
double dis(Point, Point);
int cmp_x(const void *, const void*);
int cmp_y(const void *, const void*);
int merge(Point *, Point *, int, int, int);
inline double min(double, double);
int main()
{
int n, i;
double d;
scanf("%d", &n);
while (n)
{
for (i = 0; i < n; i++)
scanf("%lf%lf", &(a[i].x), &(a[i].y));
qsort(a, n, sizeof(a[0]), cmp_x);
for (i = 0; i < n; i++)
a[i].index = i;
memcpy(b, a, n *sizeof(a[0]));
qsort(b, n, sizeof(b[0]), cmp_y);
d = closest(a, b, c, 0, n - 1);
printf("%.2lf\n", d/2);
scanf("%d", &n);
}
return 0;
}
double closest(Point a[], Point b[], Point c[], int p, int q)
{
if (q - p == 1)
return dis(a[p], a[q]);
if (q - p == 2)
{
double x1 = dis(a[p], a[q]);
double x2 = dis(a[p + 1], a[q]);
double x3 = dis(a[p], a[p + 1]);
if (x1 < x2 && x1 < x3)
return x1;
else if (x2 < x3)
return x2;
else
return x3;
}
int m = (p + q) / 2;
int i, j, k;
double d1, d2;
for (i = p, j = p, k = m + 1; i <= q; i++)
if (b[i].index <= m)
c[j++] = b[i];
//数组c左半部保存划分后左部的点, 且对y是有序的.
else
c[k++] = b[i];
d1 = closest(a, c, b, p, m);
d2 = closest(a, c, b, m + 1, q);
double dm = min(d1, d2);
merge(b, c, p, m, q); //数组c左右部分分别是对y坐标有序的, 将其合并到b.
for (i = p, k = p; i <= q; i++)
if (fabs(b[i].x - b[m].x) < dm)
c[k++] = b[i];
//找出离划分基准左右不超过dm的部分, 且仍然对y坐标有序.
for (i = p; i < k; i++)
for (j = i + 1; j < k && c[j].y - c[i].y < dm; j++)
{
double temp = dis(c[i], c[j]);
if (temp < dm)
dm = temp;
}
return dm;
}
double dis(Point p, Point q)
{
double x1 = p.x - q.x, y1 = p.y - q.y;
return sqrt(x1 *x1 + y1 * y1);
}
int merge(Point p[], Point q[], int s, int m, int t)
{
int i, j, k;
for (i = s, j = m + 1, k = s; i <= m && j <= t;)
{
if (q[i].y > q[j].y)
p[k++] = q[j], j++;
else
p[k++] = q[i], i++;
}
while (i <= m)
p[k++] = q[i++];
while (j <= t)
p[k++] = q[j++];
memcpy(q + s, p + s, (t - s + 1) *sizeof(p[0]));
return 0;
}
int cmp_x(const void *p, const void *q)
{
double temp = ((Point*)p)->x - ((Point*)q)->x;
if (temp > 0)
return 1;
else if (fabs(temp) < eps)
return 0;
else
return - 1;
}
int cmp_y(const void *p, const void *q)
{
double temp = ((Point*)p)->y - ((Point*)q)->y;
if (temp > 0)
return 1;
else if (fabs(temp) < eps)
return 0;
else
return - 1;
}
inline double min(double p, double q)
{
return (p > q) ? (q): (p);
}
版本二：（使用STL，未能AC掉,还得继续测试。。。）
#include <iostream>
#include <cmath>
#include <vector>
#include <algorithm>
#include <iomanip>
using namespace std;
const double eps = 0.00001;
class point
{
public:
point(double x1=0.0f,double y1=0.0f,int id=0):x(x1),y(y1),id(id)
{
}
~point()
{
}
double getX()const
{
return x;
}
double getY()const
{
return y;
}
void setID(int t)
{
id = t;
}
double getID()const
{
return id;
}
double Distance(const point& rhs)
{//计算与另外一个点之间的距离
double dx = (x-rhs.x);
double dy = (y-rhs.y);
return sqrt(dx*dx+dy*dy);
}
friend ostream& operator << (ostream& out,const point& rhs)
{
out<<rhs.x<<" "<<rhs.y<<" id is:"<<rhs.id<<endl;
return out;
}
bool operator < (const point& rhs)
{
return x<rhs.x;
}
point& operator = (const point& rhs)
{
x = rhs.x;
y = rhs.y;
id = rhs.id;
return *this;
}
private:
double x;
double y;
int id;//点的编号
};
bool cmp_onY(const point& p,const point& q)
{
return p.getY()<q.getY();
}
double min(const double& a,const double &b)
{
return a<b?a:b;
}
void printVector(vector<point>& v)
{
vector<point>::iterator iter;
for(iter = v.begin();iter!=v.end();++iter)
{
cout<<*iter<<endl;
}
}
int merge(vector<point>& a,vector<point>& b,int begin,int mid,int end)
{//合并
int i, j, k;
for (i = begin, j = mid + 1, k = begin; i <= mid && j <= end;)
{
if (b[i].getY() > b[j].getY())
a[k++] = b[j], j++;
else
a[k++] = b[i], i++;
}
while (i <= mid)
a[k++] = b[i++];
while (j <= end)
a[k++] = b[j++];
vector<point>::iterator iter = a.begin();
copy(iter+begin,iter+(end-begin+1),b.begin());
return 0;
}
double Closest(vector<point>& a,vector<point>& b,vector<point>& c,int begin,int last)
{
int len = last-begin;
if(len==1)
{//只有两个了
return a[begin].Distance(a[last]);
}
if(len==2)
{//还有三个
double t1 = a[begin].Distance(a[last]);
double t2 = a[begin].Distance(a[begin+1]);
double t3 = a[begin+1].Distance(a[last]);
if(t1<t2 && t1<t3)
return t1;
else if(t2<t3)
return t2;
else
return t3;
}
int mid = (begin+last)/2;//分割点
int i,j,k;
double d1,d2;
for(i = begin,j = begin,k = mid+1;i<=last;++i)
{
if(b[i].getID()<=mid)
c[j++] = b[i];
else
c[k++] = b[i];
}
d1 = Closest(a,c,b,begin,mid);
d2 = Closest(a,c,b,mid+1,last);
double dm = min(d1,d2);
merge(b,c,begin,mid,last);
for(i=begin,k=begin;i<=last;++i)
if(fabs(b[i].getX()-b[mid].getX()) < dm)
c[k++] = b[i];
for(i=begin;i<k;++i)
for(j = i+1;j<k&&(c[j].getY()-c[i].getY()<dm);j++)
{
double temp = c[i].Distance(c[j]);
if(temp<dm)
dm = temp;
}
return dm;
}
int main()
{
int nPoints,i;
double x1,y1,result=0.0f;
vector<point> v1,v2,v3;
while(cin>>nPoints&&nPoints!=0)
{
for(i=0;i<nPoints;++i)
{
cin>>x1>>y1;
point tmp(x1,y1);
v1.push_back(tmp);
}
v3 = v1;
sort(v1.begin(),v1.end());
for(i=0;i<nPoints;++i)
{
v1[i].setID(i);
}
v2 = v1;
sort(v2.begin(),v2.end(),cmp_onY);
result = Closest(v1,v2,v3,0,nPoints-1);
cout<<setiosflags(ios::fixed)<<setprecision(2);
cout<<result/2<<endl;
v1.erase(v1.begin(),v1.end());
v2.erase(v2.begin(),v2.end());
v3.erase(v3.begin(),v3.end());
}
return 0;
}
本文转自Phinecos(洞庭散人)博客园博客，原文链接：http://www.cnblogs.com/phinecos/archive/2007/12/26/1015609.html，如需转载请自行联系原作者
