题解
二分一个横坐标，过这个横坐标做一条和y轴平行的直线，相当于在这条直线上做区间覆盖，如果区间有交的话，那么答案是True
否则的话取两个不相交的区间，如果这两个圆相离或相切则不合法
否则看看相交的部分在二分的横坐标的左边还是右边，进行更新
代码
#include <bits/stdc++.h>
#define fi first
#define se second
#define pii pair<int,int>
#define pdi pair<db,int>
#define mp make_pair
#define pb push_back
#define enter putchar('\n')
#define space putchar(' ')
#define eps 1e-8
#define mo 974711
#define MAXN 100005
//#define ivorysi
using namespace std;
typedef long long int64;
typedef double db;
template<class T>
void read(T &res) {
res = 0;char c = getchar();T f = 1;
while(c < '0' || c > '9') {
if(c == '-') f = -1;
c = getchar();
}
while(c >= '0' && c <= '9') {
res = res * 10 + c - '0';
c = getchar();
}
res *= f;
}
template<class T>
void out(T x) {
if(x < 0) {x = -x;putchar('-');}
if(x >= 10) {
out(x / 10);
}
putchar('0' + x % 10);
}
int N,tot;
bool dcmp(db a,db b) {
return fabs(a - b) < eps;
}
struct Point {
db x,y;
Point(db _x = 0.0,db _y = 0.0) {
x = _x;y = _y;
}
friend Point operator + (const Point &a,const Point &b) {
return Point(a.x + b.x,a.y + b.y);
}
friend Point operator - (const Point &a,const Point &b) {
return Point(a.x - b.x,a.y - b.y);
}
friend db operator * (const Point &a,const Point &b) {
return a.x * b.y - a.y * b.x;
}
friend Point operator * (const Point &a,const db &d) {
return Point(a.x * d,a.y * d);
}
friend Point operator / (const Point &a,const db &d) {
return Point(a.x / d,a.y / d);
}
friend db dot(const Point &a,const Point &b) {
return a.x * b.x + a.y * b.y;
}
db norm() {
return x * x + y * y;
}
};
struct Circle {
Point O;
db R;
}C[MAXN];
struct line {
db s,t;
int id;
friend bool operator < (const line &a,const line &b) {
return a.t < b.t || (a.t == b.t && a.s < b.s);
}
}L[MAXN];
db dis(Point a,Point b) {
return sqrt((b - a).norm());
}
int check(db mid) {
tot = 0;
for(int i = 1 ; i <= N ; ++i) {
if(fabs(mid - C[i].O.x) >= C[i].R) {
if(mid > C[i].O.x) return -1;
else return 1;
}
db t = sqrt(C[i].R * C[i].R - (C[i].O.x - mid) * (C[i].O.x - mid));
L[++tot] = (line){C[i].O.y - t,C[i].O.y + t,i};
}
sort(L + 1,L + tot + 1);
db a = L[1].s,b = L[1].t;
for(int i = 2 ; i <= N ; ++i) {
a = max(a,L[i].s);b = min(b,L[i].t);
}
if(a + eps < b) return 0;
for(int i = 2 ; i <= N ; ++i) {
if(L[i].s >= L[1].t) {
int u = L[1].id,v = L[i].id;
if(dis(C[u].O,C[v].O) >= C[u].R + C[v].R) return -2;
else {
Point p = C[u].O + (C[v].O - C[u].O) * (C[u].R / dis(C[v].O,C[u].O));
if(p.x < mid) return -1;
else return 1;
}
}
}
}
void Solve() {
read(N);
for(int i = 1 ; i <= N ; ++i) {
scanf("%lf%lf%lf",&C[i].O.x,&C[i].O.y,&C[i].R);
}
db L = C[1].O.x - C[1].R,R = C[1].O.x + C[1].R;
for(int i = 2 ; i <= N ; ++i) {
L = min(L,C[i].O.x - C[i].R);
R = max(R,C[i].O.x + C[i].R);
}
int cnt = 50;
while(cnt--) {
db mid = (L + R) / 2;
int x = check(mid);
if(x == -2) {puts("NO");return;}
if(x == 0) {puts("YES");return;}
if(x == -1) {R = mid;}
else {L = mid;}
}
if(check(L) != 0) puts("NO");
else puts("YES");
}
int main() {
#ifdef ivorysi
freopen("f1.in","r",stdin);
#endif
Solve();
return 0;
}