1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include<cstring>
#include<cstdio>
#include<queue>
#include<algorithm>
using namespace std;
typedef long long LL;
const int maxn = 1500+5;
struct Circle{
    int x, y, r;
}cir[maxn];
//判断两个圆是否相交或相切 
bool connect(Circle &c1, Circle &c2) {
    LL dis = 1LL*(c1.x-c2.x)*(c1.x-c2.x)+1LL*(c1.y-c2.y)*(c1.y-c2.y);
    LL rad = 1LL*(c1.r+c2.r)*(c1.r+c2.r);
    return rad>=dis;
}
int vis[maxn];
bool bfs(int s, int n, int h) {
    int high = cir[s].y+cir[s].r, low = cir[s].y-cir[s].r;
    vis[s] = 1;
    queue<int>Q;
    Q.push(s);
    while(!Q.empty()) {
        int cur = Q.front(); Q.pop();
        for(int i = 0; i < n; ++i) {
            if(!vis[i] && connect(cir[cur], cir[i])) {
                high = max(high, cir[i].y+cir[i].r);
                low = min(low, cir[i].y-cir[i].r);
                vis[i] = 1;
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX