KDTree笔记

  1 #include <bits/stdc++.h>
  2 
  3 using std::min;
  4 using std::max;
  5 const int N = 100000 + 233;
  6 int n, now, maximum, minimum, siz, ans = 0x3f3f3f3f;
  7 
  8 inline int read() {
  9     int a = 0; char c = getchar();
 10     while (!isdigit(c)) c = getchar();
 11     while (isdigit(c)) a = a * 10 + c - ‘0‘, c = getchar();
 12     return a;
 13 }
 14 
 15 class KDTree {
 16 private:
 17     struct Point {
 18         int x[2];
 19         friend bool operator <(Point a, Point b) {
 20             return a.x[now] < b.x[now];
 21         }
 22     } point[N];
 23     int dis(const Point &a, const Point &b) {
 24         return abs(a.x[0] - b.x[0]) + abs(a.x[1] - b.x[1]);
 25     }
 26 
 27     struct Node {
 28         Node *ch[2];
 29         Point pt;
 30         int mini[2], maxi[2];
 31         void redef(Point a) {
 32             pt = a, mini[0] = maxi[0] = a.x[0], mini[1] = maxi[1] = a.x[1];
 33             ch[0] = ch[1] = NULL;
 34         }
 35         void update(Node *a) {
 36             mini[0] = min(mini[0], a -> mini[0]);
 37             maxi[0] = max(maxi[0], a -> maxi[0]);
 38             mini[1] = min(mini[1], a -> mini[1]);
 39             maxi[1] = max(maxi[1], a -> maxi[1]);
 40         }
 41         void pushup() {
 42             if (ch[0]) update(ch[0]);
 43             if (ch[1]) update(ch[1]);
 44         }
 45         int calc_min(Point a) {
 46             return max(mini[0] - a.x[0], 0) + max(a.x[0] - maxi[0], 0) + 
 47                 max(mini[1] - a.x[1], 0) + max(a.x[1] - maxi[1], 0);
 48         }
 49         int calc_max(Point a) {
 50             return max(abs(a.x[0] - mini[0]), abs(a.x[0] - maxi[0])) +
 51                 max(abs(a.x[1] - mini[1]), abs(a.x[1] - maxi[1]));
 52         }
 53     } *root, node[N];
 54     void build(Node *&p, int l, int r, int d) {
 55         if (l > r) return;
 56         p = node + (siz++), now = d;
 57         int mid = (l + r) >> 1;
 58         std::nth_element(point + l, point + mid, point + r + 1);
 59         p -> redef(point[mid]);
 60         build(p -> ch[0], l, mid - 1, d ^ 1);
 61         build(p -> ch[1], mid + 1, r, d ^ 1);
 62         p -> pushup();
 63     }
 64     void query_max(Node *p, Point cmp) {
 65         if (p == NULL) return;
 66         maximum = max(dis(p -> pt, cmp), maximum);
 67         int Dis[2] = {
 68             p -> ch[0] == NULL ? 0 : p -> ch[0] -> calc_max(cmp),
 69             p -> ch[1] == NULL ? 0 : p -> ch[1] -> calc_max(cmp)
 70         };
 71         int first = Dis[0] > Dis[1] ? 0 : 1;
 72         if (Dis[first] > maximum) query_max(p -> ch[first], cmp);
 73         if (Dis[first ^ 1] > maximum) query_max(p -> ch[first ^ 1], cmp);
 74     }
 75     void query_min(Node *p, Point cmp) {
 76         if (p == NULL) return;
 77         if (dis(p -> pt, cmp)) minimum = min(dis(p -> pt, cmp), minimum);
 78         int Dis[2] = {
 79             p -> ch[0] == NULL ? 0x3f3f3f3f : p -> ch[0] -> calc_min(cmp),
 80             p -> ch[1] == NULL ? 0x3f3f3f3f : p -> ch[1] -> calc_min(cmp)
 81         };
 82         int first = Dis[0] < Dis[1] ? 0 : 1;
 83         if (Dis[first] < minimum) query_min(p -> ch[first], cmp);
 84         if (Dis[first ^ 1] < minimum) query_min(p -> ch[first ^ 1], cmp);
 85     }
 86 public:
 87     KDTree() {
 88         for (int i = 1; i <= n; i++)
 89             point[i].x[0] = read(), point[i].x[1] = read();    
 90         build(root, 1, n, 0);
 91     }
 92     int ask_max(int id) {
 93         maximum = 0, query_max(root, point[id]);
 94         return maximum;
 95     }
 96     int ask_min(int id) {
 97         minimum = 0x3f3f3f3f, query_min(root, point[id]);
 98         return minimum;
 99     }
100 };
101 
102 signed main() {
103     n = read();
104     static KDTree *KDT = new KDTree();
105     for (int i = 1; i <= n; i++) 
106         ans = min(ans, KDT -> ask_max(i) - KDT -> ask_min(i));
107     printf("%d\n", ans);
108     return 0;
109 }