分类 ZOJ 下的文章

Quoit Design

题目链接

[ZOJ 2107] Quoit Design

题解

中档题。给定一些平面上的点,求最近点对。
模板题。

代码

#include <cmath>
#include <iomanip>
#include <iostream>
#include <algorithm>
using namespace std;
const int MAXN = 100005;

struct point {
    double x, y;  /*用于记录坐标点*/
    bool isRight;
}num[MAXN], a[MAXN];

inline double squ(double a) {
    return a * a;
}

inline double dis(point &a, point &b) {
    return sqrt(squ(a.x - b.x) + squ(a.y - b.y));
}

inline bool cmpx(point &a, point &b) {
    return a.x == b.x ? a.y < b.y : a.x < b.x;
}

inline bool cmpy(point &a, point &b) {
    return a.y == b.y ? a.x < b.x : a.y < b.y;
}

double find(int l, int r) {
    if (r - l == 0)    return 0;
    else if (r - l == 1)return dis(num[l], num[r]);
    else if (r - l == 2)return min(dis(num[l], num[l + 1]), min(dis(num[l + 1], num[r]), dis(num[l], num[r])));
    else {
        double ans, temp;
        int mid = (l + r) / 2;
        int p = 0;
        ans = min(find(l, mid), find(mid + 1, r));
        for (int i = l; i <= mid; i++) {
            temp = num[mid].x - ans;
            if (num[i].x >= temp) {
                a[p].isRight = false;
                a[p].x = num[i].x;
                a[p].y = num[i].y;
                p++;
            }
        }
        for (int i = mid + 1; i <= r; i++) {
            temp = num[mid].x + ans;
            if (num[i].x <= temp) {
                a[p].isRight = true;
                a[p].x = num[i].x;
                a[p].y = num[i].y;
                p++;
            }
        }
        sort(a, a + p, cmpy);
        for (int i = 0; i < p; i++)
            if (!a[i].isRight)
                for (int j = 1; (j <= 7) && (i + j < p); j++)
                    if (a[i + j].isRight)
                        ans = min(dis(a[i], a[i + j]), ans);
        return ans;
    }
}


int main()
{
    int n;
    while (cin >> n && n != 0) {
        for (int i = 0; i < n; i++)
            cin >> num[i].x >> num[i].y;
        sort(num, num + n, cmpx);
        cout << fixed << setprecision(2) << find(0, n - 1) / 2 << endl;
    }
}