Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- using ll = long long;
- using ld = long double;
- ll ts;
- ll ans;
- void solvext(ll j, ll n, vector<ld> &axx, vector<ld> &axy, vector<ld> &r, vector<bool> &usg)
- {
- for (int i = 0; i < n; i++)
- {
- if (usg.at(i) == false)
- {
- 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)));
- if (dis >= max(r.at(i), r.at(j)) / 2 && dis <= r.at(i) + r.at(j))
- {
- ts += 1;
- usg.at(j) = true;
- solvext(i, n, axx, axy, r, usg);
- }
- }
- }
- }
- void solve(ll pos, ll n, vector<ld> &axx, vector<ld> &axy, vector<ld> &r)
- {
- for (int i = 0; i < n; i++)
- {
- ts = 1;
- vector<bool> usg(n, false);
- usg.at(i) = true;
- for (int j = 0; j < n; j++)
- {
- if (usg.at(j) == false)
- {
- 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)));
- if (dis >= max(r.at(i), r.at(j)) / 2 && dis <= r.at(i) + r.at(j))
- {
- ts += 1;
- usg.at(j) = true;
- solvext(j, n, axx, axy, r, usg);
- }
- }
- if (ts > ans)
- {
- ans = ts;
- }
- }
- }
- }
- int main()
- {
- ll n;
- while (cin >> n && n != -1)
- {
- vector<ld> axx(n);
- vector<ld> axy(n);
- vector<ld> r(n);
- ans = 1;
- for (int i = 0; i < n; i++)
- {
- cin >> axx.at(i) >> axy.at(i) >> r.at(i);
- }
- solve(0, n, axx, axy, r);
- if (ans == 1)
- {
- cout << "The largest component contains " << ans << " ring." << endl;
- }
- else
- {
- cout << "The largest component contains " << ans << " rings." << endl;
- }
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment