fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define FOR(i, a, b) for(int i = (a), _b = (b); i <= _b; ++i)
  3. #define fi first
  4. #define se second
  5. #define el "\n"
  6. #define pb push_back
  7. #define sz(a) (int)a.size()
  8. #define FILL(a, x) memset(a, x, sizeof(a))
  9.  
  10. using namespace std;
  11. typedef long long ll;
  12. typedef pair<ll, ll> ii;
  13. const int N = (int)1e6 + 3;
  14.  
  15. struct Edge {
  16.     int u, v;
  17.     long double w;
  18. };
  19.  
  20. ii a[200];
  21. Edge b[N];
  22. int par[N];
  23. int n, m;
  24. long double W, C;
  25.  
  26. ll dist2(ii x, ii y) {
  27.     ll dx = x.fi - y.fi;
  28.     ll dy = x.se - y.se;
  29.     return dx * dx + dy * dy;
  30. }
  31.  
  32. int FindSet(int u) {
  33.     if (par[u] < 0) return u;
  34.     return par[u] = FindSet(par[u]);
  35. }
  36.  
  37. void UnionSet(int u, int v) {
  38.     if (par[u] > par[v]) swap(u, v);
  39.     par[u] += par[v];
  40.     par[v] = u;
  41. }
  42.  
  43. bool cmp(const Edge &x, const Edge &y) {
  44.     return x.w < y.w;
  45. }
  46.  
  47. long double Solve1() {
  48.     if (n == 1) return 0.0L;
  49.     FOR(i, 1, n) par[i] = -1;
  50.     long double S = 0.0L;
  51.     int dem = 0;
  52.     FOR(i, 1, m) {
  53.         int u = b[i].u;
  54.         int v = b[i].v;
  55.         if (u == n + 1 || v == n + 1) continue;
  56.         int fu = FindSet(u);
  57.         int fv = FindSet(v);
  58.         if (fu != fv) {
  59.             UnionSet(fu, fv);
  60.             S += b[i].w;
  61.             ++dem;
  62.             if (dem == n - 1) break;
  63.         }
  64.     }
  65.     return S;
  66. }
  67.  
  68. long double Solve2() {
  69.     FOR(i, 1, n + 1) par[i] = -1;
  70.     long double S = 0.0L;
  71.     int dem = 0;
  72.     FOR(i, 1, m) {
  73.         int u = b[i].u;
  74.         int v = b[i].v;
  75.         int fu = FindSet(u);
  76.         int fv = FindSet(v);
  77.         if (fu != fv){
  78.             UnionSet(fu, fv);
  79.             S += b[i].w;
  80.             ++dem;
  81.             if (dem == n) break;
  82.         }
  83.     }
  84.     return S;
  85. }
  86.  
  87. int main() {
  88.     ios_base::sync_with_stdio(false);
  89.     cin.tie(NULL); cout.tie(NULL);
  90.     //freopen("KETNOI.inp", "r", stdin);
  91.     //freopen("KETNOI.out", "w", stdout);
  92.  
  93.     cin >> n;
  94.     FOR(i, 1, n) cin >> a[i].fi >> a[i].se;
  95.     cin >> W >> C;
  96.  
  97.     m = 0;
  98.     FOR(i, 1, n)
  99.        FOR(j, i + 1, n){
  100.             ++m;
  101.             b[m].u = i;
  102.             b[m].v = j;
  103.             b[m].w = C * sqrtl((long double)dist2(a[i], a[j]));
  104.         }
  105.  
  106.     FOR(i, 1, n){
  107.         ++m;
  108.         b[m].u = i;
  109.         b[m].v = n + 1;
  110.         b[m].w = W;
  111.     }
  112.  
  113.     sort(b + 1, b + m + 1, cmp);
  114.  
  115.     long double ans1 = Solve1();
  116.     long double ans2 = Solve2();
  117.     long double ans = ans1 < ans2 ? ans1 : ans2;
  118.  
  119.     cout << fixed << setprecision(10) << ans;
  120.     return 0;
  121. }
  122.  
  123.  
Success #stdin #stdout 0s 5776KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0.0000000000
https://ideone.com/tNSrhO
language:
C++14 (clang 8.0)
created:
7 hours 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!