题目链接:https://codeforces.com/gym/101915/problem/J
思路:将所有相交的圆用并查集维护看做一个整体,然后枚举每个整体的左边界和右边界,判断能不能同时覆盖整个路。
AC代码:
1 #include<bits/stdc++.h> 2 using namespace std; 3 typedef long long ll; 4 const int maxn = 1e5 + 5; 5 int n; 6 struct circle{ 7 ll x, y, r; 8 }; 9 circle c[maxn]; 10 bool intercircle(circle a, circle b) 11 { 12 ll d = (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y); 13 ll r = a.r + b.r; 14 if(d <= r * r) return true; 15 else return false; 16 } 17 int far[maxn], L[maxn], R[maxn]; 18 int find(int x) 19 { 20 if(far[x] == x) return x; 21 else return far[x] = find(far[x]); 22 } 23 void unite(int x, int y) 24 { 25 x = find(x); 26 y = find(y); 27 if(x == y) return; 28 far[x] = y; 29 } 30 void init(int n) 31 { 32 for(int i = 0;i <= n;i++) 33 { 34 far[i] = i; 35 L[i] = R[i] = 0; 36 } 37 } 38 int main() 39 { 40 std::ios::sync_with_stdio(false); 41 int t; 42 cin >> t; 43 while(t--) 44 { 45 ll w, l; 46 cin >> n >> w >> l; 47 init(n); 48 for(int i = 0;i < n;i++) cin >> c[i].x >> c[i].y >> c[i].r; 49 for(int i = 0;i < n;i++) 50 { 51 for(int j = 0;j < i;j++) 52 { 53 if(intercircle(c[i],c[j])) unite(i, j); 54 } 55 } 56 for(int i = 0;i < n;i++) 57 { 58 if(c[i].x - c[i].r <= 0) L[find(i)] = 1; 59 if(c[i].x + c[i].r >= w) R[find(i)] = 1; 60 } 61 int ans = 0; 62 for(int i = 0;i < n;i++) 63 { 64 if(L[i] && R[i]) ans++; 65 } 66 cout << ans << endl; 67 } 68 return 0; 69 }