题目描述：

给你n（50000）个不相交的圆，告诉你各个圆的xy坐标和半径，问你最近的两个圆之间的距离（两圆心之间的距离减去各自的半径）

解题报告：

         暴力的做法扫描任意两圆之间的最近距离，取最小值，n^2复杂度，超时。

         正解为：

二分枚举每个圆半径的增量mid。

         那么此时的每个圆i的半径为R[i] + mid（R[i]为这个圆原来的半径），对于这组新的半径，如果在n个圆中存在两个圆相交，那么就说明mid偏大，反之，如果不存在，则mid偏小。这样就可以达到二分的目的。

         二分的复杂度可以在此近似为logn，那么问题转化为：怎样在O(n)或者O(nlogn)的时间内检测出n个圆内是否存在相交的情况，答案是“扫描线”。

         常见的扫描线通常利用在正方形的各种检测和求和：在x方向从左到右扫描，y方向用set或者线段树维护当前的线段位置即可，如果覆盖相同的线段即相交。

         如下：

    http://s1/middle/64675f54t9b24d29d0530&6903124 二分 扫描线 最近圆对 (纠正小错误）" TITLE="HDU 3124 二分 扫描线 最近圆对 (纠正小错误）" />

从左到右依次扫描竖直的四条线段ABCD，

A：插入1~3的线段

B：插入0~2的线段，和现存的1~3线段冲突，所以存在相交情况。

C：删除1~3线段

D：删除0~2线段

         但是现在是圆形，从左到右扫描，一个圆的开始位置和结束位置之间，这个圆的纵向线段长度是在不断变化的，需要另外的一种方法。

         这里采用两条扫描线，均是从左向右，每次检测的是这两条扫描线之间的圆的碰撞情况。

如图：

http://s2/middle/64675f54t9b24d41fba11&6903124 二分 扫描线 最近圆对 (纠正小错误）" TITLE="HDU 3124 二分 扫描线 最近圆对 (纠正小错误）" />

         第一条扫描线从左往右依次是每个圆的左边界，即竖直线L1，L2，L3。

         第二条扫描线从左往右依次是每个圆的右边界，即竖直线R1，R2，R3。

         两条扫描线均是从最左边的L1和R1开始，保证L扫描线的x坐标永远小于R扫描线的x坐标即可。扫描流程如下，假设有n个圆，i为Li，j为Rj：

         i = j = 1

         while(i <= n or j <= n)

         {

                   if(i == n + 1) 删除圆j，j++;

                   else if (j == n + 1) 插入圆i，检测圆i的圆心和y方向相邻两圆的碰撞情况。i++。

                   else if (i <= n and Li 在Ri的左边)

                            插入圆i，检测圆i的圆心和y方向相邻两圆的碰撞情况。i++。

                   else 删除圆j，j++;

         }

简要解释如下：

While中有4个分支

前两个是边界情况，很容易理解。

第三个是L扫描线的推进，即插入圆。

第四个条件：由于只需检测Li 和 Rj两条扫描线之间的圆的相交情况，所以，Li之前的圆都需要删除

当扫描线为Li和Rj时，已经插入的圆都是x方向起点小于等于Li，x方向终点大于等于Rj，即在Li和Rj之间是连续不间断的，所以只需检测插入圆的圆心的上下相邻的两个即可，不可能跳跃。即假设圆心位置从下到上一次编号1~m，那么插入圆x后，不可能出现x和x+2相交而不和x+1相交的情况（应为在Li和Rj之间是连续的）。

至于检测的方法就是线段树或者set了。

上图的扫描线过程是：

初始为L1,R1

L1 < R1, 插入圆A，检测无碰撞，变为L2，R1

L2 < R1, 插入圆B，检测无碰撞，变为L3, R1

L3 > R1, 删除圆B，变为L3，R2

L3 < R2，插入圆C，检测到碰撞，结束

 

代码如下：

#include<iostream>

#include<cstdio>

#include<cstring>

#include<set>

#include<algorithm>

#include<cmath>

using namespace std;

#define size 50000

#define eps 1e-8

#define sqr(x) ((double)(x) * (x))

int Left[size], Right[size], Up[size], up_rank[size];

int X[size], Y[size], R[size];

int t, n;

double mid;

set<int> mytree;

typedef set<int>::iterator it;

bool cmp_left(const int &a, const int &b){return (X[a] - R[a] < X[b] - R[b]);}

bool cmp_right(const int &a, const int &b){return (X[a] + R[a] < X[b] + R[b]);}

bool cmp_up(const int &a, const int &b){if (Y[a] == Y[b]) return X[a] < X[b]; else return Y[a] < Y[b];}

bool collid(int a, int b)

{

    a = Up[a];

    b = Up[b];

    return (sqr(X[a] - X[b]) + sqr(Y[a] - Y[b]) - sqr(R[a] + R[b] + mid + mid) <= 0);

}

bool insert(int &id)

{

    it i = mytree.insert(id).first;

    if (i != mytree.begin())

    {

        if (collid(id, *--i))

            return false;

        ++i;

    }

    if (++i != mytree.end())

    {

        if (collid(id, *i))

            return false;

    }

    return true;

}

bool remove(int v) {

    it i = mytree.find(v);

    if (i != mytree.begin() && i != --mytree.end()) {

        int a = *--i;

        ++i;

        int b = *++i;

        if (collid(a, b)) {

            return false;

        }

    }

    mytree.erase(v);

    return true;

}

bool judge()

{

    mytree.clear();

    int l = 0, r = 0;

    while(l < n || r < n)

    {

        if (r == n

        ||l != n && (X[Right[r]] + R[Right[r]] + mid) - (X[Left[l]] - R[Left[l]] - mid) >= 0)

        {

            if (!insert(up_rank[Left[l++]])) return true;

        }

        else if (!remove(up_rank[Right[r++]]))

            return true;

    }

    return false;

}

double jeogia()

{

    for(int i = 0; i < n; i++)

        Left[i] = Right[i] = Up[i] = i;

    sort(Left, Left + n, cmp_left);

    sort(Right, Right + n, cmp_right);

    sort(Up, Up + n, cmp_up);

    for(int i = 0; i < n; i++)

        up_rank[Up[i]] = i;

    double s = 0, t = sqrt(sqr(X[0] - X[1]) + sqr(Y[0] - Y[1])) - R[0] - R[1];

    while(t - s >= eps)

    {

        mid = (s + t) * 0.5; //mid 为各个圆需要加上的半径长度

        if (judge()) t = mid;//是否有圆相交

        else s = mid;

    }

    return t + s;

}

int main()

{

    scanf("%d", &t);

    while(t-- && scanf("%d", &n))

    {

        for(int i = 0; i < n; i++)

            scanf("%d%d%d", &X[i], &Y[i], &R[i]);

        printf("%.6f\n", jeogia());

    }

    return 0;

}