比赛 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;
}