HDU1007 Quoit Design-白红宇

题目地址：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，如需转载请自行联系原作者