fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. using ll = long long;
  4. #define F first
  5. #define S second
  6. #define Nanami signed
  7. #define eb emplace_back
  8. #define MASK(i) (1 << (i))
  9. #define BIT(x, i) (((x) >> (i)) & 1)
  10. #define f(i, l, r) for(int i = l; i <= r; ++i)
  11. #define e(i, l, r) for(int i = l; i >= r; --i)
  12. const int mod = 1e9 + 7;
  13. const int dom = 998244353;
  14. const int ars = 3e5 + 5;
  15. const int ii = 1e9;
  16. const ll il = 1e18;
  17.  
  18. #define db double
  19. int n, m[205]; db dist[205][205];
  20. pair<db, db> p[205][205];
  21. vector<tuple<int, int, ll>> edges;
  22.  
  23. int par[205], sz[205];
  24. void Build(){
  25.     f(i, 1, n){
  26.         par[i] = i;
  27.         sz[i] = 1;
  28.     }
  29. }
  30.  
  31. int Find(int u){
  32.     return par[u] == u ? u : par[u] = Find(par[u]);
  33. }
  34.  
  35. bool Union(int u, int v){
  36.     u = Find(u);
  37.     v = Find(v);
  38.     if(u == v) return 0;
  39.     if(sz[u] < sz[v]) swap(u, v);
  40.     sz[u] += sz[v];
  41.     par[v] = u;
  42.     return 1;
  43. }
  44.  
  45. void Kruskal(){
  46.     ll res = 0;
  47.     sort(edges.begin(), edges.end(), [&](auto &a, auto & b){
  48.         return get<2>(a) < get<2>(b);
  49.     });
  50.     for(auto [u, v, w] : edges){
  51.         if(Union(u, v)){
  52.             res += w;
  53.         }
  54.     }
  55.     cout << res;
  56. }
  57.  
  58. double sqr_side(pair<db, db> x, pair<db, db> y){
  59.     return (x.F - y.F) * (x.F - y.F) + (x.S - y.S) * (x.S - y.S);
  60. }
  61.  
  62. bool type(pair<db, db> a, pair<db, db> B, pair<db, db> C){
  63.     db aB = sqr_side(a, B);
  64.     db BC = sqr_side(B, C);
  65.     db Ca = sqr_side(C, a);
  66.     return (aB + BC > Ca and BC + Ca > aB);
  67. }
  68.  
  69. double h(pair<db, db> a, pair<db, db> B, pair<db, db> C){
  70.     db s_2 = abs((B.F - a.F) * (C.S - a.S) - (C.F - a.F) * (B.S - a.S));
  71.     db BC = sqrt(sqr_side(B, C));
  72.     return s_2 / BC;
  73. }
  74.  
  75. void xuly(int i, int j){
  76.     pair<double, double> B, C;
  77.     f(k, 1, m[i]) f(l, 1, m[j]){
  78.         B = p[j][l], C = p[j][l - 1];
  79.         if(type(p[i][k], B, C)){
  80.             double H = h(p[i][k], B, C);
  81.             dist[i][j] = min(dist[i][j], H);
  82.             dist[j][i] = min(dist[j][i], H);
  83.         }else{
  84.             dist[i][j] = min({dist[i][j], 
  85.                                 sqrt(sqr_side(p[i][k], B)), 
  86.                                 sqrt(sqr_side(p[i][k], C))});
  87.             dist[j][i] = min({dist[j][i],
  88.                                 sqrt(sqr_side(p[i][k], B)),
  89.                                 sqrt(sqr_side(p[i][k], C))});
  90.         }
  91.     }
  92.  
  93. }
  94.  
  95. Nanami main(){
  96.     ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  97.     cin >> n;
  98.     Build();
  99.     f(i, 1, n){
  100.         cin >> m[i]; 
  101.         f(j, 1, m[i]) cin >> p[i][j].F >> p[i][j].S;
  102.         p[i][0] = p[i][m[i]];
  103.     }
  104.     f(i, 0, n) f(j, 0, n) dist[i][j] = (db)il;
  105.  
  106.     f(i, 1, n){
  107.         f(j, i + 1, n){
  108.             xuly(i, j); xuly(j, i);
  109.             ll cost = (ll)floor(dist[i][j] * 1000000);
  110.             edges.eb(i, j, cost);
  111.         }
  112.     }
  113.  
  114.     Kruskal();
  115.  
  116.  
  117.     return 0;
  118. }
Success #stdin #stdout 0.01s 5276KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/XVbqXK
language:
C++14 (gcc 8.3)
created:
5 days 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!