fork(1) download
copy 
  1.     ////////////////////////////////////////
  2.     //  Problem : UVA 10034
  3.     ////////////////////////////////////////
  4.  
  5.     #include <iostream>
  6.     #include <stdio.h>
  7.     #include <vector>
  8.     #include <cctype>
  9.     #include <stdlib.h>
  10.     #include <numeric>
  11.     #include <string.h>
  12.     #include <algorithm>
  13.     #include <math.h>
  14.     #include <queue>
  15.     #include <stack>
  16.     #include <iterator>
  17.     #include <set>
  18.     #include <sstream>
  19.     #include <map>
  20.     //#include <windows.h>
  21.     using namespace std;
  22.  
  23.     #define FOR(i, a, b) for (int i = (a) ; i < (b); i++)
  24.     #define sz size()
  25.     #define pb push_back
  26.     #define clean(t) memset ((t) , -1, sizeof(t))
  27.     #define VI vector <int>
  28.     #define VS vector <string>
  29.     #define scan(n) scanf("%d", &n)
  30.     #define QI queue <int>
  31.     #define inf (1 << 29)
  32.     #define i_am_here cout << "I am here"
  33.     #define esp 1e-5
  34.     int points;
  35.     int pr[110];
  36.  
  37.  
  38.     struct co_ordinate{
  39.         float x;
  40.         float y;
  41.     };
  42.  
  43.     struct edge{
  44.         int u, v;
  45.         float w;
  46.  
  47.     };
  48.  
  49.     vector <edge> e;
  50.  
  51.     bool cmp(edge a, edge b)
  52.     {
  53.        return (a.w < b.w) ;
  54.     }
  55.  
  56.     /*float val (float a)
  57.     {
  58.         return (a > 0 ) ? a : -a;
  59.     }*/
  60.  
  61.  
  62.     float lenth (co_ordinate a, co_ordinate b)
  63.     {
  64.         return sqrt( ((a.x-b.x)*(a.x-b.x)) + ((a.y - b.y)*(a.y - b.y)) );
  65.     }
  66.  
  67.     int find(int r)
  68.     {
  69.         return (pr[r] == r)? r:find(pr[r]);
  70.     }
  71.  
  72.  
  73.  
  74.     float mst(int n)
  75.     {
  76.         int i;
  77.         FOR(i, 1, n+1)  pr[i] = i;
  78.         sort(e.begin(), e.end(), cmp);
  79.  
  80.         int count = 0;
  81.         float sum;
  82.         for (int j = 0; j < (int) e.sz; j++)
  83.         {
  84.             int x = find(e[j].u);
  85.             int y = find(e[j].v);
  86.  
  87.             if(x!=y)
  88.             {
  89.                 pr[x] = y;
  90.                 sum = sum +e[j].w;
  91.                 count++;
  92.                 if(count == n-1)    break;
  93.             }
  94.         }
  95.  
  96.         return sum;
  97.     }
  98.  
  99.  
  100.     co_ordinate storer[110];
  101.  
  102.     int main()
  103.     {
  104.  
  105.         int t;
  106.         cin >> t;
  107.         int i;
  108.         FOR(i, 1 , t+1)
  109.         {
  110.             cin >> points;
  111.             int j;
  112.             FOR(j, 1, points + 1)
  113.             {
  114.                 co_ordinate a;
  115.                 float p, q;
  116.                 cin >> p >> q;
  117.                 a.x = p; a.y = q;
  118.  
  119.                 storer[j] = a;
  120.             }
  121.  
  122.             int r, s;
  123.             for (r = 1; r <= points-1; r++)
  124.             {
  125.                 for(s = r+1; s <= points; s++)
  126.                 {
  127.                     edge get;
  128.                     get.u = r; get.v = s;
  129.                     get.w = lenth(storer[r], storer[s]);
  130.                     e.pb(get);
  131.                 }
  132.             }
  133.             cout << fixed;
  134.             cout.precision(2);
  135.  
  136.            cout <<  mst(points) +esp << endl;
  137.            e.clear();
  138.  
  139.            if(i!=t)cout << endl;
  140.  
  141.            //END OF TESTCASE
  142.         }
  143.  
  144.         return 0;
  145.     }
  146.  
Success #stdin #stdout 0s 3036KB
comments (?)
stdin
copy 
1

3
1.0 1.0
2.0 2.0
2.0 4.0
stdout
copy 
nan
https://ideone.com/QwUIBZ
language:
C++ (gcc 8.3)
created:
11 years 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!