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
11
12 public class Edge implements Comparable<Edge>
13 {
14
15 public int a, b;
16
17
18 public double length;
19
20
21
22
23
24
25
26 public Edge( int aa, int bb, double len )
27 {
28 a = aa;
29 b = bb;
30 length = len;
31 }
32
33
34
35
36
37
38
39 public int compareTo( Edge e )
40 {
41 return Double.compare( length, e.length );
42 }
43 }
44
45
46
47
48
49
50
51
52
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
63
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
83
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
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
99 double total = 0.0;
100 while( !pq.isEmpty() )
101 {
102 Edge e = pq.poll();
103
104
105 if( set[e.a] != set[e.b] )
106 {
107
108 total += e.length;
109
110
111
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
131
132
133
134
135 public static void main( String[] args ) throws Exception
136 {
137 new undergroundcables().doit();
138 }
139
140 }