编程之美2.11――寻找最近点对（POJ 3714） - c++编程基础

minum == min_l)
{
result[0] = res1[0];
result[1] = res1[1];
}
else
{
result[0] = res2[0];
result[1] = res2[1];
}
// 对[p[mid+1]-minum, p[mid]+minum]的带状区域按y排序
vector yvec;
int i, j;
for (i=mid+1; i<=r; i++)
if (p[i].m_x - p[mid].m_x < minum)
yvec.push_back(Point(p[i]));
for (i=mid; i>=l; i--)
if (p[mid+1].m_x - p[i].m_x < minum)
yvec.push_back(Point(p[i]));
sort(yvec.begin(), yvec.end(), cmpY);
for (i=0; i {
// 至多只有与其后最多7个点的距离会小于minum
for (j=i+1; j j<=i+7; j++)
{
double delta = dist(yvec[i],yvec[j]);
if (delta < minum)
{
minum = delta;
result[0] = yvec[i];
result[1] = yvec[j];
}
}
}
return minum;
}

int main()
{
int n, i, j, x, y;
vector result(2);
vector input;
cin >> n;
for (i=0; i {
cin >> x;
cin >> y;
input.push_back(Point(x,y));
}
double minum = minDifferent(input, 0, input.size()-1, result);
cout << "nearest point: " << result[0] << " and "
<< result[1] << endl;
cout << "distance: " << minum << endl;
return 0;
}
POJ 3714 问题：
平面上有两类点，计算属于不同类的顶点对的最小值。
解法：参考http://blog.csdn.net/smsmn/article/details/5963487
算法思想与上面基本相同，但编程方式上进行了改变，更好理解。下面的代码写法上完全按照参考代码的思路，只是将数组操作改为vector，但提交到POJ 3714上却会TLE，看来动态分配空间所占用的时间也不小。所以要想AC，请使用参考代码。
[cpp]
#include
#include
#include
#include
using namespace std;

const double INF = 1e100;

struct Point
{
double x, y;
int flag; // 顶点的类别
Point(){} www.2cto.com
Point(double xx, double yy):x(xx),y(yy){}

};

vector p;

bool cmp1(const Point& a, const Point& b)
{
return a.x < b.x;
}

bool cmp2(int a, int b)
{
return p[a].y < p[b].y;
}

double dist(const Point& a, const Point& b)
{
double xx = a.x - b.x;
double yy = a.y - b.y;
return sqrt(xx*xx+yy*yy);
}

// 输出属于不同类的顶点对的最小值
double min_dist(vector p, int left, int right)
{
int mid = (left+right)>>1, i,j;
if (left>=right) return INF;
for (i=mid; i>=left && p[mid].x<=p[i].x; i--);
double minum = min_dist(p, left, i);
for (i=mid; i<=right && p[i].x<=p[mid].x; i++);
minum = min(minum, min_dist(p, i, right));
vector yp;
for (i=mid; i>=left && p[mid].x-p[i].x yp.push_back(i);
for (i=mid+1; i<=right && p[i].x-p[mid].x yp.push_back(i);
// 这个方法非常巧妙，直接对顶点索引进行排序，减少了空间使用，
// 代码上也更加简洁
sort(yp.begin(), yp.end(), cmp2);
for (i=0; i for (j=i+1; j // 主要的不同之处，产生最小距离的点对必须属于不同类别
if (p[yp[j]].flag != p[yp[i]].flag)
minum = min(minum, dist(p[yp[j]], p[yp[i]]));
return minum;
}

int main()
{
int i,j,test;
cin >> test;
while (test--)
{
int xx,yy,n;
cin >> n;
for (i=0; i {
cin >> xx >> yy;
p.push_back(Point(xx,yy));
p[i].flag = 1;
}
for (; i<2*n; i++)
{
cin >> xx >> yy;
p.push_back(Point(xx,yy));
p[i].flag = 2;
}
// 按照x坐标对点集进行排序
sort(p.begin(), p.end(), cmp1);
printf("%.3lf\n", min_dist(p, 0, p.size()-1));
}
}
作者：linyunzju

编程之美2.11――寻找最近点对（POJ 3714）(二)