fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. #define ff first
  4. #define ss second
  5. #define pb push_back
  6. #define mp make_pair
  7. #define ins insert
  8. #define sz(a) ((int)(a.size()))
  9. #define mask(n) (1LL << (n))
  10. #define bit(n, i) ((n) >> (i) & 1)
  11.  
  12. using namespace std;
  13. using ll = long long;
  14. using ld = long double;
  15.  
  16. const int N = 200005;
  17.  
  18. struct pt {
  19.     ll x, y, r;
  20.     pt(): x(), y(), r() {}
  21.     pt(ll _x, ll _y, ll _r): x(_x), y(_y), r(_r) {}
  22.     int operator<(const pt& o) {
  23.         if (x == o.x) {
  24.             return y < o.y;
  25.         }
  26.         return x < o.x;
  27.     }
  28. };
  29.  
  30. ll n;
  31. pt a[N];
  32.  
  33. namespace sub1 {
  34.     int check() {
  35.         return n <= 20;
  36.     }
  37.  
  38.     int vis[N];
  39.     vector<int> g[N];
  40.  
  41.     ll disqr(pt a, pt b) {
  42.         return (b.x - a.x) * (b.x - a.x) + (b.y - a.y) * (b.y - a.y);
  43.     }
  44.  
  45.     void dfs(int u) {
  46.         vis[u] = 1;
  47.         for (int v: g[u]) {
  48.             if (!vis[v]) dfs(v);
  49.         }
  50.     }
  51.  
  52.     void solve() {
  53.         for (int i = 1; i <= n; ++i) {
  54.             for (int j = 1; j <= n; ++j) {
  55.                 if (i == j) continue;
  56.                 if (disqr(a[i], a[j]) <= a[i].r * a[i].r) {
  57.                     g[i].pb(j);
  58.                 }
  59.             }
  60.         }
  61.         ll ans = (ll)(1e18);
  62.         for (int msk = 0; msk < mask(n); ++msk) {
  63.             for (int i = 1; i <= n; ++i) {
  64.                 vis[i] = 0;
  65.             }
  66.             ll sum = 0;
  67.             for (int i = 0; i < n; ++i) {
  68.                 if (bit(msk, i) && !vis[i+1]) {
  69.                     dfs(i+1);
  70.                     ++sum;
  71.                 }
  72.             }
  73.             int ok = 1;
  74.             for (int i = 1; i <= n; ++i) {
  75.                 if (!vis[i]) {
  76.                     ok = 0;
  77.                     break;
  78.                 }
  79.             }
  80.             if (!ok) continue;
  81.             ans = min(ans, sum);
  82.         }
  83.         cout << ans << "\n";
  84.     }
  85. }
  86.  
  87. namespace sub2 {
  88.     int check() {
  89.         return n <= 1000;
  90.     }
  91.  
  92.     ll id, cnt, on[N], in[N], low[N], num[N], pat[N];
  93.     stack<int> st;
  94.     vector<int> g[N];
  95.  
  96.     ll disqr(pt a, pt b) {
  97.         return (b.x - a.x) * (b.x - a.x) + (b.y - a.y) * (b.y - a.y);
  98.     }
  99.  
  100.     void scc(int u) {
  101.         on[u] = 1;
  102.         st.push(u);
  103.         low[u] = num[u] = ++id;
  104.         for (int v: g[u]) {
  105.             if (!num[v]) {
  106.                 scc(v);
  107.                 low[u] = min(low[u], low[v]);
  108.             }
  109.             if (on[v]) {
  110.                 low[u] = min(low[u], num[v]);
  111.             }
  112.         }
  113.         if (low[u] == num[u]) {
  114.             ++cnt;
  115.             int v = -1;
  116.             while (v != u) {
  117.                 v = st.top();
  118.                 st.pop();
  119.                 on[v] = 0;
  120.                 pat[v] = cnt;
  121.             }
  122.         }
  123.     }
  124.  
  125.     void solve() {
  126.         for (int i = 1; i <= n; ++i) {
  127.             for (int j = 1; j <= n; ++j) {
  128.                 if (i == j) continue;
  129.                 if (disqr(a[i], a[j]) <= a[i].r * a[i].r) {
  130.                     g[i].pb(j);
  131.                 }
  132.             }
  133.         }
  134.         cnt = id = 0;
  135.         for (int u = 1; u <= n; ++u) {
  136.             if (!num[u]) scc(u);
  137.         }
  138.         for (int u = 1; u <= n; ++u) {
  139.             for (int v: g[u]) {
  140.                 if (pat[u] != pat[v]) {
  141.                     ++in[pat[v]];
  142.                 }
  143.             }
  144.         }
  145.         ll ans = 0;
  146.         for (int u = 1; u <= cnt; ++u) {
  147.             ans += (in[u] == 0);
  148.         }
  149.         cout << ans << "\n";
  150.     }
  151. }
  152.  
  153. namespace subfull {
  154.     int check() {
  155.         return 1;
  156.     }
  157.  
  158.     const int M = 1e6 + 5;
  159.  
  160.     ll id, cnt, on[N], in[N], low[N], num[N], pat[N];
  161.     stack<int> st;
  162.     pt b[N];
  163.     vector<pair<pt, int>> vts[3*M];
  164.     map<pair<ll, ll>, ll> rep;
  165.     vector<int> g[N];
  166.  
  167.     ll disqr(pt a, pt b) {
  168.         return (b.x - a.x) * (b.x - a.x) + (b.y - a.y) * (b.y - a.y);
  169.     }
  170.  
  171.     ll bin(ll x, ll v) {
  172.         ll l = 0, r = sz(vts[x+M]) - 1, res = r+1;
  173.         while (l <= r) {
  174.             ll m = l + (r - l) / 2;
  175.             if (vts[x+M][m].ff.y >= v) {
  176.                 res = m;
  177.                 r = m - 1;
  178.             }
  179.             else {
  180.                 l = m + 1;
  181.             }
  182.         }
  183.         return res;
  184.     }
  185.  
  186.     void scc(int u) {
  187.         on[u] = 1;
  188.         st.push(u);
  189.         low[u] = num[u] = ++id;
  190.         for (int v: g[u]) {
  191.             if (!num[v]) {
  192.                 scc(v);
  193.                 low[u] = min(low[u], low[v]);
  194.             }
  195.             if (on[v]) {
  196.                 low[u] = min(low[u], num[v]);
  197.             }
  198.         }
  199.         if (low[u] == num[u]) {
  200.             ++cnt;
  201.             int v = -1;
  202.             while (v != u) {
  203.                 v = st.top();
  204.                 st.pop();
  205.                 on[v] = 0;
  206.                 pat[v] = cnt;
  207.             }
  208.         }
  209.     }
  210.  
  211.     void solve() {
  212.         int m = 0;
  213.         for (int i = 1; i <= n; ++i) {
  214.             if (!rep.count(mp(a[i].x, a[i].y))) {
  215.                 rep[mp(a[i].x, a[i].y)] = a[i].r;
  216.                 b[++m] = a[i];
  217.             }
  218.             else {
  219.                 rep[mp(a[i].x, a[i].y)] = max(rep[mp(a[i].x, a[i].y)], a[i].r);
  220.             }
  221.         }
  222.         n = m;
  223.         for (int i = 1; i <= n; ++i) {
  224.             a[i] = pt(b[i].x, b[i].y, rep[mp(b[i].x, b[i].y)]);
  225.         }
  226.         sort(a+1, a+n+1);
  227.         for (int i = 1; i <= n; ++i) {
  228.             vts[a[i].x+M].pb(mp(a[i], i));
  229.         }
  230.         int edg = 0;
  231.         for (int i = 1; i <= n; ++i) {
  232.             for (ll x = a[i].x-a[i].r; x <= a[i].x+a[i].r; ++x) {
  233.                 ll p = bin(x, a[i].y-a[i].r);
  234.                 while (p < sz(vts[x+M]) && vts[x+M][p].ff.y <= a[i].y + a[i].r) {
  235.                     if (disqr(vts[x+M][p].ff, a[i]) <= a[i].r * a[i].r) {
  236.                         g[i].pb(vts[x+M][p].ss);
  237.                         if (++edg >= (int)(1e8)) break;
  238.                     }
  239.                     ++p;
  240.                 }
  241.                 if (edg >= (int)(1e8)) break;
  242.             }
  243.             if (edg >= (int)(1e8)) break;
  244.         }
  245.         cnt = id = 0;
  246.         for (int u = 1; u <= n; ++u) {
  247.             if (!num[u]) scc(u);
  248.         }
  249.         for (int u = 1; u <= n; ++u) {
  250.             for (int v: g[u]) {
  251.                 if (pat[u] != pat[v]) {
  252.                     ++in[pat[v]];
  253.                 }
  254.             }
  255.         }
  256.         ll ans = 0;
  257.         for (int u = 1; u <= cnt; ++u) {
  258.             ans += (in[u] == 0);
  259.         }
  260.         cout << ans << "\n";
  261.     }
  262. }
  263.  
  264. int main() {
  265.     freopen("WIFI.INP", "r", stdin);
  266.     freopen("WIFI.OUT", "w", stdout);
  267.  
  268.     ios_base::sync_with_stdio(false);
  269.     cin.tie(nullptr);
  270.  
  271.     cin >> n;
  272.     for (int i = 1; i <= n; ++i) {
  273.         cin >> a[i].x >> a[i].y >> a[i].r;
  274.     }
  275.  
  276.     if (sub1::check()) return sub1::solve(), 0;
  277.     if (sub2::check()) return sub2::solve(), 0;
  278.     subfull::solve();
  279.  
  280.     return 0;
  281. }
Success #stdin #stdout 0.03s 101512KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/4XiFtW
language:
C++ (gcc 8.3)
created:
1 day ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!