(UVA) Freckles - Solution 3

If you want to see other solutions for this problem, click here and here.

I used Prim's algorithm to solve this problem.

The difference between this solution and the previous one using Prim is that here I am not using the adjacency list to keep the freckles and their respective distances from another freckle. Instead, I calculate these distances inside the Prim method, which decreases the amount of calculations that must be done.


import java.io.*;
import java.util.*;
import java.lang.*;

class Main  {
    public static double distance(Coord f1, Coord f2) {
        return (f2.x-f1.x)*(f2.x-f1.x)+(f2.y-f1.y)*(f2.y-f1.y);
    }
   
    public static Comparator<Freckle> distComparator = new Comparator<Freckle>() {
        public int compare(Freckle f1, Freckle f2) {
            if ((f1.dist - f2.dist) < 0) {
                return -1;
            }
            else if ((f1.dist - f2.dist) > 0) {
                return 1;
            }
           
            return 0;
        }
    };
   
    public static double prim(int start, int numFreckles, Coord[] freckles) {
        Queue<Freckle> queue = new PriorityQueue<Freckle>(numFreckles, distComparator);
        Freckle f = new Freckle(start, 0);
        queue.add(f);
       
        HashSet<Integer> visited = new HashSet<Integer>();
       
        int countFreckles = 0;
        double sumDist = 0.0;
        while (queue.size() > 0) {
            Freckle curr = queue.poll();
            int currFreckle = curr.f;
            double currDist = curr.dist;
           
            if (visited.contains(currFreckle)) {
                continue;
            }
            visited.add(currFreckle);
           
            countFreckles++;
            sumDist += Math.sqrt(currDist);
            if (countFreckles == numFreckles) {
                return sumDist;
            }
           
            for (int i = 0; i < numFreckles; i++) {
                if (i == currFreckle) {
                    continue;
                }
                double d = distance(freckles[currFreckle], freckles[i]);
                f = new Freckle(i, d);
                queue.add(f);
            }
        }
       
        return -1.0;
    }
   
    public static void process() throws NumberFormatException, IOException {  
        Scanner sc = new Scanner(System.in);
       
        int numCases = sc.nextInt();
        for (int i = 0; i < numCases; i++) {
            if (i > 0) {
                System.out.println(); // blank line between two conseq cases
            }
           
            int numFreckles = sc.nextInt();
            Coord[] freckles = new Coord[numFreckles];
            for (int j = 0; j < numFreckles; j++) {
                double x = sc.nextDouble();
                double y = sc.nextDouble();
                Coord c = new Coord(x, y);
                freckles[j] = c;
            }

            double d = prim(0, numFreckles, freckles);
           
            System.out.printf("%.2f\n", d);
        }       
                                            
        return;
    }
  
    public static void main(String[] args) throws NumberFormatException, IOException {
        Main m = new Main();
        m.process();

        System.exit(0);
    }
}

class Coord {
    double x;
    double y;
   
    public Coord(double x, double y) {
        this.x = x;
        this.y = y;
    }
}

class Freckle {
    int f;
    double dist;
   
    public Freckle(int f, double dist) {
        this.f = f;
        this.dist = dist;
    }
}