比赛 |
4043级NOIP2022欢乐赛2nd |
评测结果 |
AAAAAAAAAA |
题目名称 |
平面最近点对 |
最终得分 |
100 |
用户昵称 |
lihaoze |
运行时间 |
2.342 s |
代码语言 |
C++ |
内存使用 |
17.18 MiB |
提交时间 |
2022-10-31 20:31:11 |
显示代码纯文本
#include "bits/stdc++.h"
const int N = 200010;
int n, d[N], lc[N], rc[N];
double ans = 2e18;
struct P {
double x, y;
} p[N];
double L[N], R[N], D[N], U[N];
double dist(int a, int b) {
return (p[a].x - p[b].x) * (p[a].x - p[b].x) +
(p[a].y - p[b].y) * (p[a].y - p[b].y);
}
void update(int x) {
L[x] = R[x] = p[x].x;
D[x] = U[x] = p[x].y;
if (lc[x]) {
L[x] = std::min(L[x], L[lc[x]]), R[x] = std::max(R[x], R[lc[x]]),
D[x] = std::min(D[x], D[lc[x]]), U[x] = std::max(U[x], U[lc[x]]);
}
if (rc[x]) {
L[x] = std::min(L[x], L[rc[x]]), R[x] = std::max(R[x], R[rc[x]]),
D[x] = std::min(D[x], D[rc[x]]), U[x] = std::max(U[x], U[rc[x]]);
}
}
int build(int l, int r) {
if (l > r) {
return 0;
}
int mid = (l + r) >> 1;
if (l == r) {
update(mid);
return mid;
}
double ax = 0, ay = 0, sx = 0, sy = 0;
for (int i = l; i <= r; i++) {
ax += p[i].x, ay += p[i].y;
}
ax /= double(r - l + 1), ay /= double(r - l + 1);
for (int i = l; i <= r; i++) {
sx += (p[i].x - ax) * (p[i].x - ax),
sy += (p[i].y - ay) * (p[i].y - ay);
}
if (sx >= sy) {
d[mid] = 1,
std::nth_element(p + l, p + mid, p + r + 1, [](P a, P b) {
return a.x < b.x;
});
} else {
d[mid] = 2,
std::nth_element(p + l, p + mid, p + r + 1, [](P a, P b) {
return a.y < b.y;
});
}
lc[mid] = build(l, mid - 1),
rc[mid] = build(mid + 1, r);
update(mid);
return mid;
}
double f(int a, int b) {
double ret = 0;
if (L[b] > p[a].x) ret += (L[b] - p[a].x) * (L[b] - p[a].x);
if (R[b] < p[a].x) ret += (p[a].x - R[b]) * (p[a].x - R[b]);
if (D[b] > p[a].y) ret += (D[b] - p[a].y) * (D[b] - p[a].y);
if (U[b] < p[a].y) ret += (p[a].y - U[b]) * (p[a].y - U[b]);
return ret;
}
void query(int l, int r, int x) {
if (l > r) return;
int mid = l + r >> 1;
if (mid != x) ans = std::min(ans, dist(x, mid));
if (l == r) return;
double distl = f(x, lc[mid]), distr = f(x, rc[mid]);
if (distl < ans && distr < ans) {
if (distl < distr) {
query(l, mid - 1, x);
if (distr < ans) query(mid + 1, r, x);
} else {
query(mid + 1, r, x);
if (distl < ans) query(l, mid - 1, x);
}
} else {
if (distl < ans) {
query(l, mid - 1, x);
}
if (distr < ans) {
query(mid + 1, r, x);
}
}
}
int main() {
freopen("closest.in", "r", stdin);
freopen("closest.out", "w", stdout);
std::cin >> n;
for (int i = 1; i <= n; ++ i) {
std::cin >> p[i].x >> p[i].y;
}
build(1, n);
for (int i = 1; i <= n; ++ i) {
query(1, n, i);
}
printf("%.4f", std::sqrt(ans));
return 0;
}