fork download
copy 
  1. import java.util.*;
  2. import java.io.*;
  3.  
  4. class Main
  5. {   
  6.    static Pair[] array;
  7.    static Vector<Triple> vect;
  8.    static UF uf;
  9.  
  10.    public static void main(String[] args) throws IOException
  11.    {
  12.       BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  13.  
  14.       BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));
  15.  
  16.       StringBuffer str = new StringBuffer();
  17.  
  18.       String line = br.readLine();
  19.  
  20.       while(line != null)
  21.       {
  22.          int n = Integer.parseInt(line);
  23.  
  24.          array = new Pair[n];
  25.  
  26.          vect = new Vector<Triple>();
  27.  
  28.          uf = new UF(n);
  29.  
  30.          double min = 0;
  31.  
  32.          for(int i = 0; i < n; i++)
  33.          {
  34.             line = br.readLine();
  35.  
  36.             StringTokenizer sTok = new StringTokenizer(line);
  37.  
  38.             int x = Integer.parseInt(sTok.nextToken());
  39.  
  40.             int y = Integer.parseInt(sTok.nextToken());
  41.  
  42.             array[i] = new Pair(x,y);
  43.          }
  44.  
  45.          for(int i = 0; i < n; i++)
  46.          {
  47.             for(int j = i+1; j < n; j++)
  48.             {
  49.                double d = Math.sqrt(Math.pow(array[i].x - array[j].x,2) + Math.pow(array[i].y - array[j].y,2));
  50.  
  51.                vect.add(new Triple(d,i,j));
  52.             }
  53.          }
  54.  
  55.          Collections.sort(vect);
  56.  
  57.          line = br.readLine();
  58.  
  59.          int m = Integer.parseInt(line);
  60.  
  61.          for(int i = 0; i < m; i++)
  62.          {
  63.             line = br.readLine();
  64.  
  65.             StringTokenizer sTok = new StringTokenizer(line);
  66.  
  67.             int a = Integer.parseInt(sTok.nextToken());
  68.  
  69.             int b = Integer.parseInt(sTok.nextToken());
  70.  
  71.             uf.union(a-1, b-1);
  72.          }
  73.  
  74.          for(int i = 0; i < vect.size(); i++)
  75.          {
  76.             if(uf.size() == 1)
  77.                break;
  78.  
  79.             Triple t = vect.get(i);
  80.  
  81.             double w = t.w;
  82.  
  83.             int v1 = t.v1;
  84.  
  85.             int v2 = t.v2;
  86.  
  87.             if(!uf.sameSet(v1, v2))
  88.             {
  89.                min += w;
  90.                uf.union(v1, v2);
  91.             }
  92.          }
  93.  
  94.          str.append(String.format("%.2f\n", min));
  95.  
  96.          line = br.readLine();
  97.       }
  98.  
  99.  
  100.  
  101.  
  102.  
  103.       out.write(str.toString());
  104.  
  105.       out.flush();
  106.    }
  107. }
  108.  
  109. class UF
  110. {
  111.    int[] array;
  112.    int[] sizes;
  113.    int count;
  114.  
  115.    UF(int n)
  116.    {
  117.       array = new int[n];
  118.       sizes = new int[n];
  119.       count = n;
  120.  
  121.       for(int i = 0; i < n; i++)
  122.       {
  123.          array[i] = i;
  124.          sizes[i] = 1;
  125.       }
  126.    }
  127.  
  128.    int size()
  129.    {
  130.       return count;
  131.    }
  132.  
  133.    int findSet(int i)
  134.    {
  135.       if(array[i] == i)
  136.          return i;
  137.       else
  138.          return findSet(array[i]);
  139.    }
  140.  
  141.    boolean sameSet(int i, int j)
  142.    {
  143.       return findSet(i) == findSet(j);
  144.    }
  145.  
  146.    void union(int i, int j)
  147.    {
  148.       int a = findSet(i);
  149.       int b = findSet(j);
  150.  
  151.       if(a != b)
  152.       {
  153.          if(sizes[a] > sizes[b])
  154.          {
  155.             array[b] = a;
  156.             sizes[a] += sizes[b];
  157.          }
  158.          else
  159.          {
  160.             array[a] = b;
  161.             sizes[b] += sizes[a];
  162.          }
  163.  
  164.          count--;
  165.       }
  166.    }
  167. }
  168.  
  169. class Pair
  170. {
  171.    int x;
  172.    int y;
  173.  
  174.    Pair(int a, int b)
  175.    {
  176.       x = a;
  177.       y = b;
  178.    }
  179. }
  180.  
  181. class Triple implements Comparable<Triple>
  182. {
  183.    double w;
  184.    int v1;
  185.    int v2;
  186.  
  187.    Triple(double a, int b, int c)
  188.    {
  189.       w = a;
  190.       v1 = b;
  191.       v2 = c;
  192.    }
  193.  
  194.    @Override
  195.    public int compareTo(Triple that) {
  196.       if(this.w > that.w)
  197.          return 1;
  198.       else if(this.w < that.w)
  199.          return -1;
  200.       else
  201.          return 0;
  202.    }
  203. }
Runtime error #stdin #stdout 0.08s 380224KB
comments (?)
stdin
copy 
6
0 0
200 50
100 200
50 300
300 200
300 300
2
3 4
5 6

6
0 0
200 50
100 200
50 300
300 200
300 300
5
1 2
2 3
3 4
4 5
5 6
stdout
copy 
Standard output is empty
https://ideone.com/9cxlbN
language:
Java (HotSpot 12)
created:
9 years ago
visibility:
secret

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!