hdu 1007 Quoit Design 查找平面最近点对

缘起

平面最近点对（在二维平面上的n个点中，如何快速的找出最近的一对点，就是最近点对问题） 是计算几何中的经典问题了. 遂找到 hdu 1007 Quoit Design

分析

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
输入N个点，从里边找出两个距离最短的来，算出他俩距离的一半。

【输入】
多样例. 每个样例先是一个N（2 <= N <= 100,000）.然后N行，每行是一对(x,y) 最后N=0你不需要处理这组
数据

【输出】
对每个样例，输出最小距离的一半，精确到小数点2位

【样例输入】
2
0 0
1 1
2
1 1
1 1
3
-1.5 0
0 0
0 1.5
0

【样例输出】
0.71
0.00
0.75

【限制】
5s

一种简单的想法是暴力枚举每两个点，记录最小距离，显然，时间复杂度为O(n^2)。 这题鉴于N的范围肯定被T掉. 所以本题采用分治的思想——复杂度为O(nlogn)

分治的算法是显然的——将点集分成O(n/2)的两堆, 然后分别解决子问题. 最后合并子问题. 确切讲, 求平面最近点对的算法如下

1
2
3
以x坐标排序，划中线分成两堆，递归求每堆的最近距离d，然后对两堆之间横坐标为 x[mid] - d 和 x[mid] + d 
之间的点暴力(复杂度O(n))看看是否有比 d 小的距离， 为毛是横坐标在[x[mid]-d, x[mid]+d]范围内的点? 不
然的话,一个维度的坐标超过了d, 二维的距离肯定超过了d呀~

复杂度是显然的 T(n)=2T(n/2)+O(n), 即T(n)=O(nlogn)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
//#include "stdafx.h"
#include <stdio.h>
#include <algorithm>
#include <math.h>
using namespace std;
#define SQUARE(x) ((x)*(x))
//#define LOCAL
const int maxn = 100005;
#define DBL_MAX 1.7976931348623158e+308
int n;

struct Point
{
	double x, y;
	bool operator<(Point &o) const
	{
		return x==o.x?y<o.y:x<o.x; // 按照x坐标升序
	}
}p[maxn];

double dis(int i, int j) // p[i]和p[j]之间的欧式距离
{
	return sqrt(SQUARE(p[i].x-p[j].x)+SQUARE(p[i].y-p[j].y));
}

double fz(int lo, int hi) // 解决 [lo, hi]的问题
{
	if (lo>=hi)
	{
		return DBL_MAX; // 一个点的话, 返回inf
	}
	int mid = (lo+hi)>>1;
	double a = fz(lo, mid), b = fz(mid+1, hi);
	double ans = min(a,b);
	for (int i = mid; i>=lo; i--)
	{
		if (p[mid].x-p[i].x>=ans) // 因为关于x坐标是排好序的, 所以后面的i肯定距离>=ans了, 就不必考察了
		{
			break;
		}
		for (int j = mid+1; j<=hi; j++)
		{
			if (p[j].x-p[i].x>=ans) // 如果p[j]距离p[x]的x维度都>=ans, 则同样因为关于x坐标已经排好了序, 所以不必再考察了
			{
				break;
			}
			ans = min(ans, dis(i,j)); // 优化ans
		}
	} // 别看是双重for, 但是实际跑的时候均摊复杂度到不了n^2
	return ans;
}

int main()
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
	//freopen("d:\\my.out", "w", stdout);
#endif
	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);
		printf("%.2lf\n",fz(0,n-1)/2);
	}
	return 0;
}

但是很遗憾，被T掉了. 那么上面的算法慢在哪里呢? 就在上面的双重for里面. 因为双重for本质上其实就是把中轴线（即x=p[mid].x这条直线）上下ans的距离的带型区域中的点两两遍历了一遍. 实际生产中点如果足够随机的话，肯定没问题。但是作为题目，肯定有极端数据卡你这种算法——即有太多点在这个带形区域中了(例如本身点集就比较集中, 就像下图展示的那样).导致合并子问题的复杂度还是很高. 所以还是要继续优化.

怎么优化呢? 在合并子问题的时候, 将处于带型区域的点收集起来, 然后用y坐标来做文章~ 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
//#include "stdafx.h"
#include <stdio.h>
#include <algorithm>
#include <math.h>
using namespace std;
#define SQUARE(x) ((x)*(x))
//#define LOCAL
const int maxn = 100005;
#define DBL_MAX 1.7976931348623158e+300
int n;

struct Point
{
	double x, y;
}p[maxn];
int pp[maxn]; // 用于收集处于带型区域的点集的索引

bool cmpx(Point &a, Point &b) //按照x升序
{
	return a.x<b.x;
}

bool cmpy(int a, int b) // 按照y升序
{
	return p[a].y<p[b].y;
}

double dis(int i, int j) 
{
	return sqrt(SQUARE(p[i].x-p[j].x)+SQUARE(p[i].y-p[j].y));
}

double fz(int lo, int hi)
{
	if (lo>=hi)
	{
		return DBL_MAX;
	}
	int mid = (lo+hi)>>1;
	double a = fz(lo, mid), b = fz(mid+1, hi);
	double ans = min(a,b);
	int cnt = 0; // 收集到的位于带型区域中的点的个数
	for (int i = lo; i<=hi; i++)
	{
		if (p[i].x>=p[mid].x-ans && p[i].x<=p[mid].x+ans)
		{
			pp[cnt++] = i;
		}
	} // 收集位于带型区域中的点集
	sort(pp,pp+cnt, cmpy); // 按照y坐标升序
	for (int i = 0; i<cnt-1; i++)
	{
		for (int j = i+1; j<cnt; j++)
		{
			if (p[pp[j]].y-p[pp[i]].y>=ans)
			{
				break; // 因为关于y升序排过序了
			}
			ans = min(ans, dis(pp[i],pp[j]));
		}
	}
	return ans;
}

int main()
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
	//freopen("d:\\my.out", "w", stdout);
#endif
	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); // 按照x升序
		printf("%.2lf\n",fz(0,n-1)/2);
	}
	return 0;
}

ac情况（水过水过~）

30678826 2019-09-22 20:28:42 Accepted 1007 780MS 3200K 1504 B G++ yfsyfsyfs