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

题意：

求出平面上n个点中最接近的两个点的距离。

思路：

最接近点对问题，利用分治法解决，先按照x排序，进行分治，并对每段区间内的点再按照y排序，可以证明每段区间内的比较次数为常数，复杂度为O(nlogn)。

代码：

#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; }