J. The Volcano Eruption（圆相交+并查集）

喜欢ヅ旅行 2023-06-01 11:15 8阅读 0赞

题目链接：[https://codeforces.com/gym/101915/problem/J][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 }

转载于:https://www.cnblogs.com/Carered/p/11545187.html

[https_codeforces.com_gym_101915_problem_J]: https://codeforces.com/gym/101915/problem/J