The Java Program: Cables.java
1
2
3
4
5
6 import java.io.*;
7 import java.util.Scanner;
8 import java.util.Arrays;
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26 public final class Cables {
27
28 private static final Scanner STDIN =
29 new Scanner (new BufferedInputStream (System.in));
30
31 public static void main (final String[] args) {
32
33 input: for (int ds=1; ; ds++) {
34 final int n = STDIN.nextInt();
35 if (n==0) break;
36 assert 2<=n && n<=1000;
37
38 int[] x=new int[n], y=new int[n];
39 double[] cost=new double[n];
40 boolean[] visit=new boolean [n];
41
42 for (int i=0; i<n; i++) {
43 x[i] = STDIN.nextInt(); assert -1000<=x[i] && x[i]<=1000;
44 y[i] = STDIN.nextInt(); assert -1000<=y[i] && y[i]<=1000;
45 }
46
47 Arrays.fill (cost, Double.MAX_VALUE);
48 cost[0]=0.0D;
49 double total = 0.0;
50 for (int i=0; i<cost.length; i++) {
51
52 double m=Double.MAX_VALUE; int v=-1;
53 for (int j=0; j<cost.length; j++) {
54 if (!visit[j] && cost[j]<m) { v=j; m=cost[j]; }
55 }
56 visit[v]=true;
57 total+= m;
58 for (int j=0; j<cost.length; j++) {
59 final double d = Math.hypot (x[v]-x[j],y[v]-y[j]);
60 if (d<cost[j]) cost[j]=d;
61 }
62 }
63 System.out.format ("%.2f", total);
64 }
65 }
66 }
67
68
69
70
71
72
73