Palace
Time Limit: 8000/4000 MS (Java/Others) Memory Limit: 262144/262144 K (Java/Others)
Problem Description
The last trial Venus imposes on Psyche is a quest to the underworld. She is to take a box and obtain in it a dose of the beauty of Prosperina, queen of the underworld.
There are $ n $ palaces in the underworld, which can be located on a 2-Dimension plane with $ (x, y) $ coordinates (where $ x, y $ are integers). Psyche would like to find the distance of the closest pair of two palaces. It is the password to enter the main palace.
However, the underworld is mysterious and changes all the time. At different times, exactly one of the $ n $ palaces disappears.
Psyche wonders what the distance of the closest pair of two palaces is after some palace has disappeared.
Print the sum of the distance after every single palace has disappeared.
To avoid floating point error, define the distance $ d $ between palace $ (x_1, y_1) $ and $ (x_2, y_2) $ as $ d = (x_1 - x_2) ^ 2 + (y_1 - y_2) ^ 2 $.
There are $ n $ palaces in the underworld, which can be located on a 2-Dimension plane with $ (x, y) $ coordinates (where $ x, y $ are integers). Psyche would like to find the distance of the closest pair of two palaces. It is the password to enter the main palace.
However, the underworld is mysterious and changes all the time. At different times, exactly one of the $ n $ palaces disappears.
Psyche wonders what the distance of the closest pair of two palaces is after some palace has disappeared.
Print the sum of the distance after every single palace has disappeared.
To avoid floating point error, define the distance $ d $ between palace $ (x_1, y_1) $ and $ (x_2, y_2) $ as $ d = (x_1 - x_2) ^ 2 + (y_1 - y_2) ^ 2 $.
Input
The first line of the input contains an integer $ T $ $ (1 \le T \le 5) $, which denotes the number of testcases.
For each testcase, the first line contains an integers $ n $ $ (3 \le n \le 10 ^ 5) $, which denotes the number of temples in this testcase.
The following $ n $ lines contains $ n $ pairs of integers, the $ i $-th pair $ (x, y) $ $ (-10 ^ 5 \le x,y \le 10 ^ 5) $ denotes the position of the $ i $-th palace.
For each testcase, the first line contains an integers $ n $ $ (3 \le n \le 10 ^ 5) $, which denotes the number of temples in this testcase.
The following $ n $ lines contains $ n $ pairs of integers, the $ i $-th pair $ (x, y) $ $ (-10 ^ 5 \le x,y \le 10 ^ 5) $ denotes the position of the $ i $-th palace.
Output
For each testcase, print an integer which denotes the sum of the distance after every single palace has disappeared.
Sample Input
1
3
0 0
1 1
2 2
Sample Output
12
Hint
If palace $ (0,0) $ disappears,$ d = (1-2) ^ 2 + (1 - 2) ^ 2 = 2 $; If palace $ (1,1) $ disappears,$ d = (0-2) ^ 2 + (0 - 2) ^ 2 = 8 $; If palace $ (2,2) $ disappears,$ d = (0-1) ^ 2 + (0-1) ^ 2 = 2 $; Thus the answer is $ 2 + 8 + 2 = 12 $。
Source
题意
给出n个点的坐标,假设第i个点消失后,最近点对的距离的平方为d,求d的和。
思路
会发现,这n个点的最近点对的距离对答案的贡献系数为(n-2),因为除了删除这两个最近点对,其它点的删除都不会影响最近点对的距离。后面分别删除这两个点,再求出最近点对的距离求和即可。求最近点对可以用KD-tree或者CDQ分治。
KD-tree
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 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 |
#include<bits/stdc++.h> using namespace std; typedef long long LL; struct FastIO { static const int S = 1310720; int wpos; char wbuf[S]; FastIO() : wpos(0) {} inline int xchar() { static char buf[S]; static int len = 0, pos = 0; if(pos == len) pos = 0, len = fread(buf, 1, S, stdin); if(pos == len) return -1; return buf[pos ++]; } inline int xint() { int s = 1, c = xchar(), x = 0; while(c <= 32) c = xchar(); if(c == '-') s = -1, c = xchar(); for(; '0' <= c && c <= '9'; c = xchar()) x = x * 10 + c - '0'; return x * s; } inline void wchar(int x) { if(wpos == S) fwrite(wbuf, 1, S, stdout), wpos = 0; wbuf[wpos ++] = x; } inline void wint(LL x) { if(x < 0) wchar('-'), x = -x; char s[24]; int n = 0; while(x || !n) s[n ++] = '0' + x % 10, x /= 10; while(n--) wchar(s[n]); } ~FastIO() { if(wpos) fwrite(wbuf, 1, wpos, stdout), wpos = 0; } } io; const int maxn = 1e5 + 5; int idx; struct Point { int x[2]; bool enable; bool operator < (const Point &b) const { return x[idx] < b.x[idx]; } } p[maxn]; LL GetDist(Point &a, Point &b) { return (LL)(a.x[0] - b.x[0]) * (a.x[0] - b.x[0]) + (LL)(a.x[1] - b.x[1]) * (a.x[1] - b.x[1]); } void build(int L, int R, bool dep = 0) { if(L > R) return ; int mid = L + R >> 1; idx = dep ; nth_element(p + L, p + mid, p + R + 1); build(L, mid - 1, dep ^ 1); build(mid + 1, R, dep ^ 1); } void query(int L, int R, Point &local, int &ansidx, LL &ansdist, bool dep = 0) { if(L > R) return; int mid = L + R >> 1; pair<int, int> x = make_pair(L, mid - 1), y = make_pair(mid + 1, R); if(local.x[dep] >= p[mid].x[dep]) swap(x, y); query(x.first, x.second, local, ansidx, ansdist, dep ^ 1); if(p[mid].enable) { LL dis = GetDist(p[mid], local); if(dis < ansdist) { ansdist = dis; ansidx = mid; } } if((LL)(local.x[dep] - p[mid].x[dep]) * (local.x[dep] - p[mid].x[dep]) < ansdist) query(y.first, y.second, local, ansidx, ansdist, dep ^ 1); } int n; int match[maxn]; LL find_closest(int &idx1, int &idx2) { memset(match, 0, sizeof(match)); LL mindist = __LONG_LONG_MAX__; for(int i = 1; i <= n; i++) { p[i].enable = 0; LL dist = __LONG_LONG_MAX__; int id; query(1, n, p[i], id, dist); if(dist < mindist) { mindist = dist; idx1 = i; idx2 = id; } match[i] = id; p[i].enable = 1; } return mindist; } LL re_find(int id) { LL ret = __LONG_LONG_MAX__ ; p[id].enable = 0; for(int i = 1; i <= n; i++) { if(i == id) continue; if(match[i] == id) { LL dist = __LONG_LONG_MAX__; int idt; p[i].enable = 0; query(1, n, p[i], idt, dist); p[i].enable = 1; ret = min(ret, dist); } else ret = min(ret, GetDist(p[i], p[match[i]])); } p[id].enable = 1; return ret; } int main() { int T = io.xint(); while(T--) { n = io.xint(); for(int i = 1; i <= n; i++) { p[i].x[0] = io.xint(); p[i].x[1] = io.xint(); p[i].enable = 1; } build(1, n); int idx1, idx2; LL ans = find_closest(idx1, idx2) * (n - 2); if(n > 2) { ans += re_find(idx1); ans += re_find(idx2); } io.wint(ans); io.wchar('\n'); } return 0; } |
CDQ分治
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 |
#include<bits/stdc++.h> using namespace std; typedef long long LL; const int maxn = 1e5 + 5; struct Point { int x, y, idx; LL operator * (const Point &b) const { return (LL)(x - b.x) * (x - b.x) + (LL)(y - b.y) * (y - b.y); } }; void cdq(int L, int R, Point p[], int &idx1, int &idx2, LL &dist) { if(L >= R) return; if(L + 1 == R) { LL pdist = p[L] * p[R]; if(pdist < dist) { dist = pdist; idx1 = p[L].idx; idx2 = p[R].idx; } return; } int mid = L + R >> 1; cdq(L, mid, p, idx1, idx2, dist); cdq(mid + 1, R, p, idx1, idx2, dist); static Point pt[maxn]; int cnt = 0; for(int i = L; i <= R; i++) if(abs(p[i].x - p[mid].x) < dist) pt[++cnt] = p[i]; sort(pt + 1, pt + 1 + cnt, [](Point & a, Point & b) { if(a.y == b.y) return a.x < b.x; else return a.y < b.y; }); for(int i = 1; i <= cnt; i++) for(int j = i + 1; j <= cnt && pt[j].y - pt[i].y < dist; j++) { LL pdist = pt[i] * pt[j]; if(pdist < dist) { dist = pdist; idx1 = pt[i].idx; idx2 = pt[j].idx; } } } Point p[maxn], p2[maxn]; int main() { int T; scanf("%d", &T); while(T--) { int n; scanf("%d", &n); for(int i = 1; i <= n; i++) { scanf("%d %d", &p[i].x, &p[i].y); p[i].idx = i; } sort(p + 1, p + 1 + n, [](Point & a, Point & b) { if(a.x == b.x)return a.y < b.y; else return a.x < b.x; }); LL ans = 0; LL dist = __LONG_LONG_MAX__; int idx1, idx2; cdq(1, n, p, idx1, idx2, dist); ans += dist * (n - 2); int cnt = 0; for(int i = 1; i <= n; i++) if(p[i].idx != idx1) p2[++cnt] = p[i]; dist = __LONG_LONG_MAX__; cdq(1, n - 1, p2, idx1, idx1, dist); ans += dist; cnt = 0; for(int i = 1; i <= n; i++) if(p[i].idx != idx2) p2[++cnt] = p[i]; dist = __LONG_LONG_MAX__; cdq(1, n - 1, p2, idx2, idx2, dist); ans += dist; printf("%lld\n", ans); } return 0; } |