程式設計之美2.11——尋找最近點對（POJ 3714）

問題：

給定平面上N個點的坐标，找出距離最近的兩個點。

解法：

我們先對N個點的x坐标進行排序，排序我們使用最壞複雜度O(n*logn)的快速排序方法，在排序的過程中minDifferent會遞歸計算出左右兩邊的最小距離，再用其中的較小值minum得到以中位數點附近的帶狀區域[p[median+1].x-median, p[median].x+median]，對帶狀區域的點按照y坐标排序，對帶狀區域的每個點隻需計算最多7個點，就能得到所有可能小于minum的點對。

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;

// 頂點資訊
struct Point
{
	double m_x, m_y;
	Point():m_x(0.0),m_y(0.0) {}
	Point(double x, double y):m_x(x),m_y(y){}
	bool operator==(const Point& p) const 
	{return m_x==p.m_x && m_y==p.m_y;}
};

ostream& operator<<(ostream& os, const Point& p)
{
	return os << "(" << p.m_x << "," << p.m_y << ")";
}

// 插入排序
template<class T, class Pr>
void insert_sort(vector<T> &vec, int l, int r, Pr pred)
{
	int i, j;
	for (i=l+1; i<=r; i++)
	{
		T tmp = vec[i];
		for (j=i-1; j>=l && pred(tmp,vec[j]); j--) 
			vec[j+1]=vec[j];
		vec[j+1] = tmp;
	}
}

// 找到key所在的位置
template<class T>
int get_position(vector<T> &vec, int l, int r, T key)
{
	for (int i=l; i<=r; i++)
		if (key == vec[i])
			return i;
	return -1;
}

// 按第一個元素對vec進行劃分
template<class T, class Pr>
int partition(vector<T> &vec, int l, int r, Pr pred)
{
	int i, j;
	for (i=l+1,j=l; i<=r; i++)
	{
		if (pred(vec[i],vec[l]))
		{
			++j;
			swap(vec[i],vec[j]);
		}
	}
	swap(vec[j],vec[l]);
	return j;
}

// 順序統計得到第k個元素的值
template<class T, class Pr>
T select(vector<T> &vec, int l, int r, int k, Pr pred)
{
	int n = r-l+1;
	if (n==1)
	{
		if (k!=0)
			printf("Out of Boundary!\n");
		return vec[l];
	}
	// 找中位數的中位數作為分割點
	int cnt = n/5;
	int tcnt = (n+4)/5;
	int rem = n%5;
	vector<T> group(tcnt);
	int i, j;
	for (i=0,j=l; i<cnt; i++,j+=5)
	{
		insert_sort(vec, j, j+4, pred);
		group[i] = vec[j+2];
	}
	if (rem)
	{
		insert_sort(vec, j, j+rem-1, pred);
		group[i] = vec[j+(rem-1)/2];
	}
	T key = select(group, 0, tcnt-1, (tcnt-1)/2, pred);
	// 找到分割點的位置
	int key_pos = get_position(vec, l, r, key);
	swap(vec[key_pos], vec[l]);
	// 用分割點對數組進行劃分，小的在左邊，大的在右邊
	int pos = partition(vec, l, r, pred);
	int x = pos - l;
	if (x == k) return key;
	else if (x < k) 
		return select(vec, pos+1, r, k-x-1, pred);
	else
		return select(vec, l, pos-1, k, pred);
}

// 計算點a和b的距離
double dist(const Point& a, const Point& b)
{
	double x = a.m_x-b.m_x;
	double y = a.m_y-b.m_y;
	return sqrt(x*x+y*y);
}

bool cmpX(const Point& a, const Point& b)
{
	return a.m_x < b.m_x;
}

bool cmpY(const Point& a, const Point& b)
{
	return a.m_y < b.m_y;
}

double minDifferent(vector<Point> p, int l, int r, vector<Point> &result)
{
	// 按中位數進行劃分後的子區域的元素個數都會減小到2或3，不會再到1
	if ((r-l+1)==2)
	{
		result[0] = p[l];
		result[1] = p[r];
		if (cmpX(p[r],p[l])) swap(p[l], p[r]);
		return dist(p[l], p[r]);
	}
	if ((r-l+1)==3)
	{
		insert_sort(p, l, r, cmpX);
		double tmp1 = dist(p[l], p[l+1]);
		double tmp2 = dist(p[l+1], p[l+2]);
		double ret = min(tmp1, tmp2);
		if (tmp1 == ret)
		{
			result[0] = p[l];
			result[1] = p[l+1];
		}
		else
		{
			result[0] = p[l+1];
			result[1] = p[l+2];
		}
		return ret;
	}
	// 大于3個點的情況
	int mid = (r+l)>>1;
	Point median = select(p, l, r, mid-l, cmpX);
	vector<Point> res1(2), res2(2);
	double min_l = minDifferent(p, l, mid, res1);
	double min_r = minDifferent(p, mid+1, r, res2);
	double minum = min(min_l, min_r);
	if (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<Point> 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<yvec.size(); i++)
	{
		// 至多隻有與其後最多7個點的距離會小于minum
		for (j=i+1; j<yvec.size() && yvec[j].m_y-yvec[i].m_y<minum &&
			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<Point> result(2);
	vector<Point> input;
	cin >> n;
	for (i=0; i<n; 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，請使用參考代碼。

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;

const double INF = 1e100;

struct Point
{
	double x, y;
	int flag;	// 頂點的類别
	Point(){}
	Point(double xx, double yy):x(xx),y(yy){}
};

vector<Point> 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<Point> 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<int> yp;
	for (i=mid; i>=left && p[mid].x-p[i].x<minum; i--)
		yp.push_back(i);
	for (i=mid+1; i<=right && p[i].x-p[mid].x<minum; i++)
		yp.push_back(i);
	// 這個方法非常巧妙，直接對頂點索引進行排序，減少了空間使用，
	// 代碼上也更加簡潔
	sort(yp.begin(), yp.end(), cmp2);
	for (i=0; i<yp.size(); i++)
		for (j=i+1; j<yp.size() && p[yp[j]].y-p[yp[i]].y<minum; 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<n; 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));
	}
}

程式設計之美2.11——尋找最近點對（POJ 3714）

繼續閱讀

DOS指令(2) 磁盤操作類指令

寫在工作13周年

程式設計高手：VC 6.0下利用消息實作内部程序通訊

設定某一行背景顔色的CListCtrl

VS2008 不在支援 Attributed ATL

C++之父Bjarne Stroustrup的演講：軟體理想和曆史

BMP檔案結構及圖像每行位元組計算方法

linux網絡程式設計----發送與接收檔案

處理PCX檔案

各種二分查找

JAVA高效程式設計指南

C#多線程——前台線程和背景線程

Android – ListView 中添加按鈕，動态删除添加ItemView的操作

IE8 CSS設定DIV居中，添加“margin:0 auto”

Small tricks

Linux裝置模型（中）之上層容器