[HDU1007]Quoit Design

求平面内最近点对。不用K-d Tree的话,可以用分治。程序十分简洁易懂。可以用抽屉原理证明,合并的时候每次最多考虑7个点。

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
#include <cmath>
#include <cstdio>
#include <cstring>
#include <algorithm>

inline int sign(const double x)
{
  static const double EPS = 1e-8;
  if (x > EPS) return 1;
  return x < -EPS ? -1 : 0;
}
inline double sqr(const double x) { return x*x; }

const int MAXN = 100000;

struct Point
{
  double x, y;
  Point() { }
  Point(const double a, const double b):x(a), y(b) { }
};
inline bool cmpx(const Point& lhs, const Point& rhs) { return sign(lhs.x-rhs.x) < 0; }
inline bool cmpy(const Point& lhs, const Point& rhs) { return sign(lhs.y-rhs.y) < 0; }
inline double dist(const Point& a, const Point& b) { return sqr(a.x-b.x)+sqr(a.y-b.y); }

int n;
Point a[MAXN];
double solve(const int lef, const int rig)
{
  static Point p[MAXN];
  if (lef == rig) return 1e10;
  const int mid = (lef+rig)/2;
  double d = std::min(solve(lef, mid), solve(mid+1, rig));
  int cnt = 0;
  for (int i = mid; i >= lef && sign(a[mid].x-a[i].x-d) <= 0; --i) p[cnt++] = a[i];
  for (int i = mid+1; i <= rig &&sign(a[i].x-a[mid].x-d) <= 0; ++i) p[cnt++] = a[i];
  std::sort(p, p+cnt, cmpy);
  for (int j = 0; j < cnt; ++j)
    for (int k = j+1; k < cnt && k < j+7; ++k)
    {
      if (sign(p[k].y-p[j].y-d) > 0) break;
      d = std::min(d, dist(p[j], p[k]));
    }
  return d;
}
int main()
{
  while (scanf("%d", &n) != EOF && n)
  {
    for (int i = 0; i < n; ++i)
      scanf("%lf%lf", &a[i].x, &a[i].y);
    std::sort(a, a+n, cmpx);
    printf("%.2f\n", std::sqrt(solve(0, n-1)) / 2.0);
  }
}

Comments