In case of failure
Time Limit: 60000/30000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 1039 Accepted Submission(s): 425
Problem Description
To help their clients deal with faulty Cash Machines, the board of The Planar Bank has decided to stick a label expressing sincere regret and sorrow of the bank about the failure on every ATM. The very same label would gently ask the customer to calmly head
to the nearest Machine (that should hopefully
work fine).
to the nearest Machine (that should hopefully
work fine).
In order to do so, a list of two-dimensional locations of all n ATMs has been prepared, and your task is to find for each of them the one closest with respect to the Euclidean distance.
Input
The input contains several test cases. The very first line contains the number of cases t (t <= 15) that follow. Each test cases begin with the number of Cash Machines n (2 <= n <= 10^5). Each of the next n lines contain the coordinates of one Cash Machine
x,y (0 <= x,y <=10^9) separated by a space. No two
points in one test case will coincide.
x,y (0 <= x,y <=10^9) separated by a space. No two
points in one test case will coincide.
Output
For each test case output n lines. i-th of them should contain the squared distance between the i-th ATM from the input and its nearest neighbour.
Sample Input
2 10 17 41 0 34 24 19 8 28 14 12 45 5 27 31 41 11 42 45 36 27 15 0 0 1 2 2 3 3 2 4 0 8 4 7 4 6 3 6 1 8 0 11 0 12 2 13 1 14 2 15 0
Sample Output
200 100 149 100 149 52 97 52 360 97 5 2 2 2 5 1 1 2 4 5 5 2 2 2 5
Source
Recommend
lcy
题意：求每个点最近的点的距离
题解：k-d 树
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
typedef long long LL;
typedef pair<int, LL> PII;
typedef pair<int, int> pii;
const int maxn = 211222;
const int maxD = 2;
const int maxM = 12;
const LL INF = 4611686018427387903LL;
int now;
struct TPoint {
int x[maxD];
void read() {
for (int i = 0; i < 2; ++i)
scanf("%d", x + i);
}
} p[maxn];
bool cmp(const TPoint& a, const TPoint& b) {
return a.x[now] < b.x[now];
}
template<typename T> T sqr(T n) {
return n * n;
}
struct KDtree {
int K, n, top;
int split[maxn];
LL dis2[maxM];
TPoint stk[maxn];
TPoint kp[maxn];
TPoint mp;
void build(int l, int r) {
if (l >= r)
return;
int i, j, mid = (l + r) >> 1;
LL dif[maxD], mx;
for (i = 0; i < K; ++i) {
mx = dif[i] = 0;
for (j = l; j < r; ++j)
mx += kp[j].x[i];
mx /= r - l;
for (j = l; j < r; ++j)
dif[i] += sqr(kp[j].x[i] - mx);
}
now = 0;
for (i = 1; i < K; ++i)
if (dif[now] < dif[i])
now = i;
split[mid] = now;
nth_element(kp + l, kp + mid, kp + r, cmp);
build(l, mid);
build(mid + 1, r);
}
void update(const TPoint& p, int M) {
int i, j;
LL tmp = dist(p, mp);
for (i = 0; i < M; ++i)
if (dis2[i] > tmp) {
for (j = M - 1; j > i; --j) {
stk[j] = stk[j - 1];
dis2[j] = dis2[j - 1];
}
stk[i] = p;
dis2[i] = tmp;
break;
}
}
void nearest_search(int l, int r, int M) {
if (l >= r)
return;
int mid = (l + r) >> 1;
update(kp[mid], M);
if (l + 1 == r)
return;
LL d = mp.x[split[mid]] - kp[mid].x[split[mid]];
if (d <= 0) {
nearest_search(l, mid, M);
if (sqr(d) < dis2[M - 1])
nearest_search(mid + 1, r, M);
} else {
nearest_search(mid + 1, r, M);
if (sqr(d) < dis2[M - 1])
nearest_search(l, mid, M);
}
}
void find_nearest(TPoint p, int M) {
for (int i = 0; i < M; ++i) {
dis2[i] = INF;
}
mp = p;
nearest_search(0, n, M);
}
LL dist(const TPoint& a, const TPoint& b) {
LL res = 0;
for (int i = 0; i < K; ++i)
res += sqr<LL>(a.x[i] - b.x[i]);
return res;
}
} KD;
int main() {
int i, n, T;
scanf("%d", &T);
while (T--) {
scanf("%d", &n);
KD.n = n;
KD.K = 2;
for (i = 0; i < n; ++i) {
p[i].read();
KD.kp[i] = p[i];
}
KD.build(0, n);
for (i = 0; i < n; ++i) {
KD.find_nearest(p[i], 2);
printf("%I64d\n", KD.dis2[1]);
}
}
return 0;
}