Advertisement
Guest User

Untitled

a guest
Apr 18th, 2015
218
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 1.44 KB | None | 0 0
  1. package fgfgfgfgfgfgf;
  2.  
  3. import java.util.ArrayList;
  4. import java.util.Collections;
  5. import java.util.Scanner;
  6.  
  7. public class KruskullPrim {
  8.  
  9.     public static void main(String[] args) {
  10.         Scanner in = new Scanner(System.in);
  11.         int n = in.nextInt();
  12.         Coord[] c = new Coord[n];
  13.         for (int i = 0; i<n; i++){
  14.             c[i] = new Coord(in.nextDouble(), in.nextDouble(), i);
  15.         }
  16.         ArrayList<Edge> e = new ArrayList<Edge>();
  17.         for (int i = 0; i<n-1; i++){ //O(n^2)
  18.             for (int j = i+1; j<n; j++){
  19.                 e.add(new Edge(getDistance(c[i], c[j]), i, j));
  20.             }
  21.         }
  22.         Collections.sort(e); //O(n^2*log(n^2))
  23.         double res = 0;
  24.         int tc = 0;
  25.         for (int i = 0; i<e.size(); i++){ //O(n^2)
  26.             if (c[e.get(i).v1].color!=c[e.get(i).v2].color){
  27.                 c[e.get(i).v2].color = c[e.get(i).v1].color;
  28.                 res+=e.get(i).weight;
  29.                 tc++;
  30.             }
  31.             if (tc==n-1) break;
  32.         }
  33.         System.out.println(res);
  34.     }
  35.     public static double getDistance(Coord p1, Coord p2){
  36.         return Math.sqrt((p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y));
  37.     }
  38.  
  39. }
  40. class Coord{
  41.     double x;
  42.     double y;
  43.     int color;
  44.     public Coord(double x, double y, int color){
  45.         this.x = x;
  46.         this.y = y;
  47.         this.color = color;
  48.     }
  49. }
  50. class Edge implements Comparable<Edge>{
  51.     double weight;
  52.     int v1;
  53.     int v2;
  54.     public Edge(double weight, int v1, int v2){
  55.         this.weight = weight;
  56.         this.v1 = v1;
  57.         this.v2 = v2;
  58.     }
  59.     @Override
  60.     public int compareTo(Edge e) {
  61.         return Double.compare(this.weight, e.weight);
  62.     }
  63. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement