http://acm.hdu.edu.cn/showproblem.php?pid=3124
题意：给出n个相离的圆，求最近的不同圆上两点的距离
二分答案a
所有圆的半径增加a，若此时有圆相交，说明最近距离小于a
否则，最近距离大于a
如何判断是否有圆相交？
扫描线从左往右扫，用set维护此时不相交的圆，按圆心的纵坐标升序排列
扫到一个圆的最左端，判断该圆加入set会不会与set里的圆相交
因为set里的圆都已经按圆心纵坐标升序排列，只判断该圆圆心上下的两个圆
所以扫到一个圆的最右端，删除圆的时候，也要判断该圆的上下两个圆是否有交点
因为一个圆可能隔着它与另一个相交
#include<set> #include<cmath> #include<cstdio> #include<algorithm> using namespace std; #define N 50001 int n; double MID,mid; struct Circle { int x,y,r; }cir[N]; struct Line { int id; double xi; }e[N<<1]; struct node { int id; node(int id_) : id(id_) {} bool operator < (const node p) const { return id<p.id; } }; set<node>s; set<node>::iterator it,itt; bool cmp(Circle p,Circle q) { if(p.y!=q.y) return p.y<q.y; return p.x<q.x; } bool cmp2(Line p,Line q) { return p.xi<q.xi; } bool point(int i,int j) { double dis=sqrt(1.0*(cir[i].x-cir[j].x)*(cir[i].x-cir[j].x)+1.0*(cir[i].y-cir[j].y)*(cir[i].y-cir[j].y)); return cir[i].r+cir[j].r+2*mid>=dis; } bool in(int d) { if(s.empty()) { s.insert(node(d)); return true; } it=s.upper_bound(node(d)); if(it!=s.end()) if(point((*it).id%n,d)) return false; if(it==s.begin()) { s.insert(node(d)); return true; } it--; if(point((*it).id%n,d)) return false; s.insert(node(d)); return true; } bool out(int d) { s.erase(node(d)); it=s.upper_bound(node(d)); if(it==s.end()) return true; if(it==s.begin()) return true; itt=it; itt--; if(point((*it).id%n,(*itt).id%n)) return false; return true; } bool check() { // printf("%.6lf\n",MID); s.clear(); mid=MID/2; int m=0; for(int i=0;i<n;++i) { e[++m].id=i; e[m].xi=cir[i].x-cir[i].r-mid; e[++m].id=i+n; e[m].xi=cir[i].x+cir[i].r+mid; } sort(e+1,e+m+1,cmp2); int k; for(int i=1;i<=m;++i) { k=e[i].id%n; if(e[i].id<n) { if(!in(k)) return false; } else { if(!out(k)) return false; } /* it=s.begin(); while(it!=s.end()) { printf("%d",(*it).id%n); it++; } printf("\n");*/ } return true; } int main() { // freopen("data.txt","r",stdin); //freopen("my.txt","w",stdout); int T; scanf("%d",&T); double l,r; while(T--) { scanf("%d",&n); for(int i=0;i<n;++i) scanf("%d%d%d",&cir[i].x,&cir[i].y,&cir[i].r); sort(cir,cir+n,cmp); l=0,r=1000000; while(r-l>1e-10) { MID=(l+r)/2; if(check()) l=MID; else r=MID; } printf("%.6lf\n",MID); } return 0; }
Time Limit: 20000/10000 MS (Java/Others) Memory Limit: 131072/131072 K (Java/Others)
Total Submission(s): 2293 Accepted Submission(s): 820
原文：https://www.cnblogs.com/TheRoadToTheGold/p/12217505.html