Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.io.PrintWriter;
- import java.util.*;
- class Vertex{
- int x;
- int y;
- int depth;
- Vertex parent;
- // ArrayList<Integer> lists;
- public Vertex () {
- // lists = new ArrayList<>();
- depth = 0;
- parent = this;
- }
- }
- class Len implements Comparable<Len>{
- double len;
- int n;
- Vertex u;
- Vertex v;
- public Len(Vertex u, Vertex v) {
- this.v = v;
- this.u = u;
- this.len = Math.sqrt((u.x - v.x)*(u.x - v.x) + (u.y - v.y)*(u.y - v.y));
- }
- @Override
- public int compareTo(Len obj) {
- int compare = 0;
- if (this.len > obj.len)
- compare = 1;
- else if (this.len < obj.len)
- compare = -1;
- return compare;
- }
- }
- public class Kruskal {
- private Vertex Find(Vertex x) {
- Vertex root;
- if (x.parent == x)
- root = x;
- else {
- x.parent = Find(x.parent);
- root = x.parent;
- }
- return root;
- }
- private void Union(Vertex x, Vertex y) {
- Vertex rootX = Find(x);
- Vertex rootY = Find(y);
- if (rootX.depth < rootY.depth)
- rootX.parent = rootY;
- else {
- rootY.parent = rootX;
- if (rootX.depth == rootY.depth && rootX != rootY)
- rootX.depth++;
- }
- }
- private double SpanningTree(Len[] e) {
- double E = 0;
- int i = 0;
- while (i < e.length) {
- Vertex v = e[i].v;
- Vertex u = e[i].u;
- if (Find(u) != Find(v)) {
- E = E + e[i].len;
- Union(u, v);
- }
- i++;
- }
- return E;
- }
- private void MST_Kruskal(Len[] e) {
- PrintWriter pw = new PrintWriter(System.out,false);
- Arrays.sort(e);
- double a;
- a = SpanningTree(e);
- //return a;
- pw.printf("%.2f", a);
- pw.close();
- }
- public static void main(String[] args) {
- int N, x, y;
- Scanner in = new Scanner(System.in);
- N = in.nextInt();
- int M = N * N / 2;
- Vertex[] g = new Vertex[N];
- Len[] l = new Len[M];
- // for (int i = 0; i < N; i++)
- // g[i] = new Vertex();
- if(N == 1) {
- for (int i = 0; i < N; i++) {
- g[i] = new Vertex();
- x = in.nextInt();
- y = in.nextInt();
- //g[i].lists.add(y);
- //g[i].lists.add(x);
- g[i].x = x;
- g[i].y = y;
- }
- int ind = 0;
- /* for (int i = 0; i < M; i++)
- l[i] = new Len(g[0], g[0]);*/
- for (int i = 0; i < N; i++) {
- for (int j = i + 1; j < N; j++) {
- l[ind++] = new Len(g[i], g[j]);
- }
- }
- }
- else{
- for (int i = 0; i < N; i++) {
- g[i] = new Vertex();
- l[i] = new Len(g[0],g[0]);
- x = in.nextInt();
- y = in.nextInt();
- //g[i].lists.add(y);
- //g[i].lists.add(x);
- g[i].x = x;
- g[i].y = y;
- }
- int ind = 0;
- for (int i = N; i < M; i++)
- l[i] = new Len(g[0], g[0]);
- for (int i = 0; i < N; i++) {
- for (int j = i + 1; j < N; j++) {
- l[ind++] = new Len(g[i], g[j]);
- //System.out.println(ind++);
- }
- }
- }
- Kruskal k = new Kruskal();
- k.MST_Kruskal(l);
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement