The Java Program: undergroundcables.java

  1 import java.io.*;
  2 import java.util.*;
  3 
  4 public class undergroundcables 
  5 {
  6     public Scanner sc;
  7     public PrintStream ps;
  8     
  9     /**
 10      * A class to capture what we need to know about an edge.
 11      */
 12     public class Edge implements Comparable<Edge>
 13     {
 14         /** Endpoints */
 15         public int a, b;
 16         
 17         /** Length */
 18         public double length;
 19         
 20         /**
 21          * Build an Edge
 22          * @param aa First endpoint
 23          * @param bb Second endpoint
 24          * @param len Length
 25          */
 26         public Edge( int aa, int bb, double len )
 27         {
 28             a = aa;
 29             b = bb;
 30             length = len;
 31         }
 32         
 33         /**
 34          * Compare one edge to another by length
 35          * 
 36          * @param e Another edge
 37          * @return Standard Java compareTo return value
 38          */
 39         public int compareTo( Edge e )
 40         {
 41             return Double.compare( length, e.length );
 42         }
 43     }
 44     
 45     /**
 46      * Euclidean distance between two points
 47      * 
 48      * @param x1 First x
 49      * @param y1 First y
 50      * @param x2 Second x
 51      * @param y2 Second y
 52      * @return The distance between (x1,y1) and (x2,y2)
 53      */
 54     public double distance( int x1, int y1, int x2, int y2 )
 55     {
 56         double dx = x2-x1;
 57         double dy = y2-y1;
 58         return Math.sqrt( dx*dx + dy*dy );
 59     }
 60     
 61     /**
 62      * Driver.
 63      * @throws Exception
 64      */
 65     public void doit() throws Exception
 66     {
 67         sc = new Scanner( new File( "undergroundcables.judge" ) );
 68         ps = new PrintStream( new FileOutputStream( "undergroundcables.out" ) ); 
 69         
 70         int set[] = new int[1000];
 71         int xs[] = new int[1000];
 72         int ys[] = new int[1000];
 73         
 74         PriorityQueue<Edge> pq = new PriorityQueue<Edge>();
 75         
 76         for(;;)
 77         {
 78             int n = sc.nextInt();
 79             if( n==0 ) break;
 80             System.out.println( n );
 81             
 82             // Read in all of the points.
 83             // Put each point in its own set
 84             for( int i=0; i<n; i++ )
 85             {
 86                 xs[i] = sc.nextInt();
 87                 ys[i] = sc.nextInt();
 88                 set[i] = i;
 89             }
 90             
 91             // Put all of the edges on a priority queue
 92             pq.clear();
 93             for( int i=0; i<n; i++ ) for( int j=i+1; j<n; j++ )
 94             {
 95                 pq.add( new Edge( i, j, distance( xs[i], ys[i], xs[j], ys[j] ) ) );
 96             }
 97             
 98             // Go through all of the edges, smallest to largest
 99             double total = 0.0;
100             while( !pq.isEmpty() )
101             {
102                 Edge e = pq.poll();
103                 
104                 // if the two points of this edge are in different sets
105                 if( set[e.a] != set[e.b] )
106                 {
107                     // Use this edge. Add in its length
108                     total += e.length;
109                     
110                     // Merge the two sets by looking for
111                     // everything it set b, and putting them in set a.
112                     int target = set[e.b];
113                     for( int k=0; k<n; k++ )
114                     {
115                         if( set[k]==target )
116                         {
117                             set[k] = set[e.a];
118                         }
119                     }
120                 }
121             }
122             
123             ps.printf( "%.2f", total );
124             ps.println();
125             System.out.printf( "%.2f\n", total );
126         }
127     }
128     
129     /**
130      * The main just creates an object and calls doit().
131      * 
132      * @param args Command line args, necessary but unused.
133      * @throws Exception
134      */
135     public static void main( String[] args ) throws Exception
136     {
137         new undergroundcables().doit();
138     }
139 
140 }