HDU - 1007 分治(最接近点对模板)

题意：

思路：

代码：

#include <bits/stdc++.h>using namespace std;const int MAXN = 1e5 + 10;struct node {    double x, y;}px[MAXN], py[MAXN];bool cmpx (const node a, const node b) {    return a.x < b.x;}bool cmpy (const node a, const node b) {    return a.y < b.y;}double dis(node a, node b) {    return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));}double closet(int l, int r) {    if (l + 1 == r)        return dis(px[l], px[r]);    if (l + 2 == r)        return min(dis(px[l], px[r]), min(dis(px[l + 1], px[r]), dis(px[l], px[l + 1])));    int m = (l + r) >> 1;    double ans = min(closet(l, m), closet(m + 1, r));    int num = 0;    for (int i = l; i <= r; i++)        if (px[i].x >= px[m].x - ans && px[i].x <= px[m].x + ans)            py[++num] = px[i];    sort (py + 1, py + 1 + num, cmpy);    for (int i = 1; i <= num; i++) {        for (int j = i + 1; j <= num; j++) {            if (py[j].y - py[i].y >= ans) break;                 // 这一步这样写，但可以证明最多不超过6个            ans = min(ans, dis(py[i], py[j]));        }    }    return ans;}int main() {    //freopen("in.txt", "r", stdin);    int n;    while(scanf("%d", &n), n) {        for (int i = 1; i <= n; i++)            scanf("%lf%lf", &px[i].x, &px[i].y);        sort (px + 1, px + 1 + n, cmpx);        PRintf("%.2f/n", closet(1, n) / 2);    }    return 0;}