Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- package fgfgfgfgfgfgf;
- import java.util.ArrayList;
- import java.util.Collections;
- import java.util.Scanner;
- public class KruskullPrim {
- public static void main(String[] args) {
- Scanner in = new Scanner(System.in);
- int n = in.nextInt();
- Coord[] c = new Coord[n];
- for (int i = 0; i<n; i++){
- c[i] = new Coord(in.nextDouble(), in.nextDouble(), i);
- }
- ArrayList<Edge> e = new ArrayList<Edge>();
- for (int i = 0; i<n-1; i++){ //O(n^2)
- for (int j = i+1; j<n; j++){
- e.add(new Edge(getDistance(c[i], c[j]), i, j));
- }
- }
- Collections.sort(e); //O(n^2*log(n^2))
- double res = 0;
- int tc = 0;
- for (int i = 0; i<e.size(); i++){ //O(n^2)
- if (c[e.get(i).v1].color!=c[e.get(i).v2].color){
- c[e.get(i).v2].color = c[e.get(i).v1].color;
- res+=e.get(i).weight;
- tc++;
- }
- if (tc==n-1) break;
- }
- System.out.println(res);
- }
- public static double getDistance(Coord p1, Coord p2){
- return Math.sqrt((p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y));
- }
- }
- class Coord{
- double x;
- double y;
- int color;
- public Coord(double x, double y, int color){
- this.x = x;
- this.y = y;
- this.color = color;
- }
- }
- class Edge implements Comparable<Edge>{
- double weight;
- int v1;
- int v2;
- public Edge(double weight, int v1, int v2){
- this.weight = weight;
- this.v1 = v1;
- this.v2 = v2;
- }
- @Override
- public int compareTo(Edge e) {
- return Double.compare(this.weight, e.weight);
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement