平面最近点对

Posted on | Views:

分治求平面最近点对.

给出平面上的 $n$ 个点,询问不同的两个点之间距离最小是多少.

暴力

直接枚举两个点计算距离,时间复杂度 $O(n^2)$ .

kd 树

建出 kd 树,对每个点询问一下与它最近的距离.

适当剪枝,复杂度为玄学.

分治

把所有点按照 $x$ 排序,从中间划分成左右两部分,递归计算两部分内部各自的贡献,再考虑跨过中线的贡献.

记 $d$ 表示左右两部分内部贡献的最小值,那么计算跨过中线的点对时,只需要考虑距离 $<d$ 的点对.

假定中线为 $l:x=k$ ,那么只用考虑横坐标在区间 $(x-k,x+k)$ 内的点.

把这些点拿出来按照 $y$ 排序,枚举起点,向后找终点,当两者纵坐标之差达到 $k$ 时就换下一个起点.

可以证明 ,对于每个起点,有效的终点不会超过 $6$ 个.

时间复杂度 $T(n)=2T(\frac n 2) + O(n\log n)=O(n\log^2 n)$ .

模板题

Hdu 1007 Quoit Design

给出平面上 $n$ 个点,需要找出一个圆,使得它恰好包含了其中的一个点,求出这个圆可能的最大半径.

以最近点对为直径的两个端点作圆,将它做微小偏移即可得到所求的圆,半径可以直接视作最近点对距离的一半.

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
82
83
84
85
86
87
88
89
90
91
//%std
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline int read()
{
	int out = 0, fh = 1;
	char jp = getchar();
	while ((jp > '9' || jp < '0') && jp != '-')
		jp = getchar();
	if (jp == '-')
		fh = -1, jp = getchar();
	while (jp >= '0' && jp <= '9')
		out = out * 10 + jp - '0', jp = getchar();
	return out * fh;
}
void print(int x)
{
	if (x >= 10)
		print(x / 10);
	putchar('0' + x % 10);
}
void write(int x, char c)
{
	if (x < 0)
		putchar('-'), x = -x;
	print(x);
	putchar(c);
}
const int N = 1e5 + 10;
struct v2
{
	double x, y;
	v2 operator - (const v2 &rhs) const
	{
		return (v2){x - rhs.x, y - rhs.y};
	}
	double modulus()
	{
		return sqrt(x * x + y * y);
	}
	void in()
	{
		scanf("%lf%lf", &x, &y);
	}
} p[N], tmp[N];
bool cx(const v2 &A, const v2 &B)
{
	return A.x < B.x;
}
bool cy(const v2 &A, const v2 &B)
{
	return A.y < B.y;
}
double ans;
int n;
void work(int l, int r)
{
	if (l == r)
		return;
	int mid = (l + r) >> 1;
	work(l, mid);
	work(mid + 1, r);
	double k = p[mid].x;
	int t = 0;
	for (int i = l; i <= r; ++i)
		if (fabs(k - p[i].x) <= ans)
			tmp[++t] = p[i];
	sort(tmp + 1, tmp + 1 + t, cy);
	for (int i = 1; i <= t; ++i)
		for (int j = i + 1; j <= t; ++j)
			if (tmp[j].y - tmp[i].y < ans)
				ans = min(ans, (tmp[j] - tmp[i]).modulus());
			else
				break;
}
void solve()
{
	for (int i = 1; i <= n; ++i)
		p[i].in();
	sort(p + 1, p + 1 + n, cx);
	ans = 1e18;
	work(1, n);
	printf("%.2lf\n", ans / 2);
}
int main()
{
	while (n = read())
		solve();
	return 0;
}