HDOJ 1007

发表于 |

题目

给$N$个点，求最近点对的距离的一半。

数据范围

$N \leq 100000$

做法

分治。

先按x坐标分成左右2部分，则最近点对的位置有2种情况：

  1. 2个点都在左边或者都在右边
  2. 1个点在左边另1共个点在右边

对于情况1，直接递归计算即可。

对于情况2，由于我们已经递归计算了情况1，我们一定得到了一个初步的最小距离$d$。那么，在情况2中，对于距离大于$d$的点对就不用计算了。只需要计算离分划的$x_m$距离不超过$d$的点。并且，对于确定的$y_p$，为了不重复，只要计算范围在$[y_p-d, y_p]$的点。这里涉及到对y排序，由于是分治，很容易将归并排序加入其中。这样，对于确定的点$(x_p,y_p)$，其中$x_m-d \leq x_p \leq x_m + d$，只要计算一个下图所示的矩形区域。显然，左右的正方形内最多有4个点，所以矩形内最多有6个点。于是，对于每个点，只要计算5个点即可。

分治的层数是$O(log_2N)$，每层操作是$O(N)$的，所以总的复杂度是$O(N\times log_2N)$。

代码

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
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 1e5 + 5;
const double INF = 2e18;
typedef pair<double, double> P;
int N;
P A[MAX_N];
bool compare_y(P a, P b)
{
  return a.second < b.second;
}
// 传入的a已经按x排序
double closest_pair(P *a, int n)
{
  if (n <= 1) return INF;
  int m = n / 2;
  double x = a[m].first;
  double d = min(closest_pair(a, m), closest_pair(a + m, n - m));
  inplace_merge(a, a + m, a + n, compare_y);
  vector<P> b;
  for (int i = 0; i < n; ++i) {
    if (abs(a[i].first - x) >= d) continue;
    for (int j = 0; j < b.size(); ++j) {
      double dx = a[i].first - b[b.size() - j - 1].first;
      double dy = a[i].second - b[b.size() - j - 1].second;
      if (dy >= d) break;
      d = min(d, sqrt(dx * dx + dy * dy));
    }
    b.push_back(a[i]);
  }
  return d;
}
void solve()
{
  sort(A, A + N);
  printf("%.2f\n", closest_pair(A, N) / 2);
}
int main()
{
  while (scanf("%d", &N), N) {
    for (int i = 0; i < N; ++i) {
      scanf("%lf%lf", &A[i].first, &A[i].second);
    }
    solve();
  }
  return 0;
}