Prob.

求平面最近圆对,保证两两不交。

Sol.

模仿平面最近点对,分治。

Code (210ms 7.3kb)

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
const int maxn = 1e5 + 5, INF = 0x3f3f3f3f;
struct P{double r, x, y; bool operator<(const P& r)const{return x < r.x;}} p[maxn], q[maxn];
int n;
#define sqr(x) ((x) * (x))
inline double dis(P i, P j){return sqrt(sqr(i.x - j.x) + sqr(i.y - j.y));}
inline bool cmp(P i, P j){return i.y < j.y;}
double Rad;
double dc(int L = 1, int R = n)
{
    if(L == R) return INF;
    if(L + 1 == R) return dis(p[L], p[R]) - p[L].r - p[R].r;
    int M = (L + R) >> 1;
    double ans = min(dc(L, M), dc(M + 1, R));
    int qc = 0;
    for(int i = L; i <= R; ++i) if(abs(p[i].x - p[M].x) <= ans + Rad * 2)
        q[qc++] = p[i];
    sort(q, q + qc, cmp);
    for(int i = 0; i < qc; ++i) for(int j = i + 1; j < qc && abs(q[i].y - q[j].y) <= ans + Rad * 2; ++j)
        ans = min(ans, dis(q[i], q[j]) - q[i].r - q[j].r);
    return ans;
}
int main()
{
    while(scanf("%d", &n), n)
    {
        Rad = .0;
        for(int i = 1; i <= n; ++i) scanf("%lf%lf%lf", &p[i].r, &p[i].x, &p[i].y), Rad = max(Rad, p[i].r);
        sort(p + 1, p + n + 1);
        printf("%.7lf\n", dc());
    }
    return 0;
}

标签: divide and conquer

添加新评论