T3000

Untitled

Jun 6th, 2022
60
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.01 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4. using ll = long long;
  5. using ld = long double;
  6. ll ts;
  7. ll ans;
  8. void solvext(ll j, ll n, vector<ld> &axx, vector<ld> &axy, vector<ld> &r, vector<bool> &usg)
  9. {
  10.     for (int i = 0; i < n; i++)
  11.     {
  12.         if (usg.at(i) == false)
  13.         {
  14.             ld dis = sqrt((axx.at(i) - axx.at(j)) * (axx.at(i) - axx.at(j)) + (axy.at(i) - axy.at(j)) * (axy.at(i) - axy.at(j)));
  15.             if (dis >= max(r.at(i), r.at(j)) / 2 && dis <= r.at(i) + r.at(j))
  16.             {
  17.                 ts += 1;
  18.                 usg.at(j) = true;
  19.                 solvext(i, n, axx, axy, r, usg);
  20.             }
  21.         }
  22.     }
  23. }
  24. void solve(ll pos, ll n, vector<ld> &axx, vector<ld> &axy, vector<ld> &r)
  25. {
  26.     for (int i = 0; i < n; i++)
  27.     {
  28.         ts = 1;
  29.         vector<bool> usg(n, false);
  30.         usg.at(i) = true;
  31.         for (int j = 0; j < n; j++)
  32.         {
  33.             if (usg.at(j) == false)
  34.             {
  35.                 ld dis = sqrt((axx.at(i) - axx.at(j)) * (axx.at(i) - axx.at(j)) + (axy.at(i) - axy.at(j)) * (axy.at(i) - axy.at(j)));
  36.                 if (dis >= max(r.at(i), r.at(j)) / 2 && dis <= r.at(i) + r.at(j))
  37.                 {
  38.                     ts += 1;
  39.                     usg.at(j) = true;
  40.                     solvext(j, n, axx, axy, r, usg);
  41.                 }
  42.             }
  43.             if (ts > ans)
  44.             {
  45.                 ans = ts;
  46.             }
  47.         }
  48.     }
  49. }
  50.  
  51. int main()
  52. {
  53.     ll n;
  54.     while (cin >> n && n != -1)
  55.     {
  56.  
  57.         vector<ld> axx(n);
  58.         vector<ld> axy(n);
  59.         vector<ld> r(n);
  60.         ans = 1;
  61.         for (int i = 0; i < n; i++)
  62.         {
  63.  
  64.             cin >> axx.at(i) >> axy.at(i) >> r.at(i);
  65.         }
  66.         solve(0, n, axx, axy, r);
  67.         if (ans == 1)
  68.         {
  69.             cout << "The largest component contains " << ans << " ring." << endl;
  70.         }
  71.         else
  72.         {
  73.             cout << "The largest component contains " << ans << " rings." << endl;
  74.         }
  75.     }
  76.  
  77.     return 0;
  78. }
Advertisement
Add Comment
Please, Sign In to add comment