/
BAEKJOON 4386
81 lines (71 loc) · 1.71 KB
/
BAEKJOON 4386
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
public class Main {
static Edge[] edge;
static int[] parent;
static int T;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
T = Integer.parseInt(br.readLine());
double[][] arr = new double[T][2];
for (int i = 0; i < T; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
arr[i][0] = Double.parseDouble(st.nextToken());
arr[i][1] = Double.parseDouble(st.nextToken());
}
edge = new Edge[T * (T - 1) / 2];
int index = 0;
for (int i = 0; i < T - 1; i++) {
for (int j = i + 1; j < T; j++) {
double d = Math.sqrt(
Math.pow(Math.abs(arr[i][0] - arr[j][0]), 2) + Math.pow(Math.abs(arr[i][1] - arr[j][1]), 2));
edge[index++] = new Edge(i, j, d);
}
}
make();
Arrays.sort(edge, (a, b) -> Double.compare(a.v, b.v));
int cnt = 0;
double ans = 0;
for (int i = 0; i < T * (T - 1) / 2; i++) {
Edge e = edge[i];
if(find(e.s) != find(e.e)) {
union(e.s,e.e);
ans += e.v;
cnt++;
}
if(cnt == T-1)
break;
}
System.out.printf("%.2f",ans);
}
static void make() {
parent = new int[T + 1];
for (int i = 1; i <= T; i++) {
parent[i] = i;
}
}
static int find(int a) {
if (parent[a] == a)
return a;
return parent[a] = find(parent[a]);
}
static void union(int a, int b) {
int ar = find(a);
int br = find(b);
if (ar < br)
parent[br] = ar;
else
parent[ar] = br;
}
static class Edge {
int s, e;
double v;
Edge(int s, int e, double v) {
this.s = s;
this.e = e;
this.v = v;
}
}
}