Description
1tthinking随便地画了一些圆. ftiasch认为这些圆有交集（面积非零）的可能性不大。因为他实在画了太多圆，所以你被请来判断是否存在交集。
Input
第1行，一个整数 N (1 ≤ N ≤ 10), 圆的数量。
第2到 N 行: 三个整数 X, Y, R, 圆心在 (X, Y), 半径为 R 的圆。
Output
如果存在面积非零的交集，则输出 "YES"，否则输出 "NO"。
首先可以确定如果有相交，x坐标一定在区间[max(x[i]-r[i]),min(x[i]+r[i])]内
取这个区间中点M，在直线x=M上，若所有圆在这条线上有不为0的交集则可以判断存在面积非0的交集
否则找出一对圆在x=M上不相交，若两圆相离/相切则可以判断无解，否则把区间缩小到这两个圆交集所在的x坐标区间递归计算
每次缩小区间至少缩小一半，且圆的坐标和半径是整数，因此复杂度是可以保证的
#include<cstdio>
#include<cmath>
#include<cstdlib>
using namespace std;
typedef double ld;
const ld _0=1e-6l;
const int N=;
int n;
ld x[N],y[N],r[N];
ld L,R;
int read(){
int x=,c=getchar(),f=;
while(c>||c<){if(c=='-')f=-;c=getchar();}
while(c>&&c<)x=x*+c-,c=getchar();
return x*f;
}
void get(int id,ld X,ld&a,ld&b){
X-=x[id];
X=sqrt(r[id]*r[id]-X*X);
a=y[id]-X;
b=y[id]+X;
}
bool chk(ld X,int a,int b){
if(fabs(X-x[a])>r[a]||fabs(X-x[b])>r[b])return ;
ld a1,a2,b1,b2;
get(a,X,a1,a2);
get(b,X,b1,b2);
return a2>b1&&a1<b2;
}
void chk(int a,int b){
ld xd=x[b]-x[a],yd=y[b]-y[a];
ld d=sqrt(xd*xd+yd*yd);
if(d+_0>r[a]+r[b]){
puts("NO");
exit();
}
ld s=(r[a]+r[b]+d)/.;
ld h=*sqrt(s*(s-r[a])*(s-r[b])*(s-d))/d;
ld m=x[a]+xd*sqrt(r[a]*r[a]-h*h)/d,c=h*fabs(yd)/d;
if(d*d+r[a]*r[a]<r[b]*r[b])m=x[a]*-m;
ld lx=m-c,rx=m+c;
if(lx>x[a]-r[a]&&chk(x[a]-r[a]+_0,a,b))lx=x[a]-r[a];
if(lx>x[b]-r[b]&&chk(x[b]-r[b]+_0,a,b))lx=x[b]-r[b];
if(rx<x[a]+r[a]&&chk(x[a]+r[a]-_0,a,b))rx=x[a]+r[a];
if(rx<x[b]+r[b]&&chk(x[b]+r[b]-_0,a,b))rx=x[b]+r[b];
if(lx>L)L=lx;
if(rx<R)R=rx;
}
int main(){
n=read();
for(int i=;i<n;i++){
x[i]=read();
y[i]=read();
r[i]=read();
}
L=x[]-r[],R=x[]+r[];
for(int i=;i<n;i++){
if(L<x[i]-r[i])L=x[i]-r[i];
if(R>x[i]+r[i])R=x[i]+r[i];
}
while(){
if(L+_0>R){
puts("NO");
return ;
}
ld M=(L+R)/.;
ld y1,y2,a1,a2;
get(,M,y1,y2);
for(int i=;i<n;i++){
get(i,M,a1,a2);
if(a1>y1)y1=a1;
if(a2<y2)y2=a2;
if(y1+_0>y2){
for(int j=;j<i;j++){
get(j,M,y1,y2);
if(y1>=a2-_0||y2<=a1+_0){
chk(i,j);
goto re;
}
}
}
}
puts("YES");
return ;
re:;
}
}