HDU 1007

    技术2024-07-10  66

    // 最近点对模板 #include <iostream> #include <algorithm> #include <cmath> using namespace std; const int MAXN = 100005; struct POINT { double x, y; int index; void input() { scanf("%lf %lf", &x, &y); } }X[MAXN], Y[MAXN]; bool cmpx(const POINT &a, const POINT &b) { return a.x < b.x; } bool cmpy(const POINT &a, const POINT &b) { return a.y < b.y; } double dis(const POINT &a, const POINT &b) { return sqrt((a.x-b.x) * (a.x-b.x) + (a.y-b.y) * (a.y-b.y)); } double min_dis(int a, int b, POINT *Y) { double ans = 1e8; if (b-a <= 2) { for (int i = a; i < b; ++i) { for (int j = i+1; j <= b; ++j) { double temp = dis(X[i], X[j]); if (ans > temp) ans = temp; } } return ans; } int mid = (a+b) / 2; POINT *Yl = new POINT[mid-a+1]; POINT *Yr = new POINT[b-mid]; int i, j, k, ind; for (i = 0, j = 0, k = 0; i <= b-a; ++i) { if (Y[i].index <= mid) Yl[j++] = Y[i]; else Yr[k++] = Y[i]; } double left_min = min_dis(a, mid, Yl); double right_min = min_dis(mid+1, b, Yr); ans = min(left_min, right_min); double line = X[mid].x; for (i = 0, ind = 0; i <= b-a; ++i) { if (fabs(Y[i].x - line) < ans) Y[ind++] = Y[i]; } for (i = 0; i < ind - 1; ++i) { for (j = i+1; j <= i+7 && j < ind; ++j) { double temp = dis(Y[i], Y[j]); if (ans > temp) ans = temp; } } delete []Yl; delete []Yr; return ans; } int main() { int n, i; while (scanf("%d", &n), n) { for (i = 0; i < n; ++i) X[i].input(); sort(X, X+n, cmpx); for (i = 0; i < n; ++i) X[i].index = i; memcpy(Y, X, n * sizeof(POINT)); sort(Y, Y+n, cmpy); printf("%.2lf\n", min_dis(0, n-1, Y) / 2); } return 0; }
    最新回复(0)