(UVA) Getting in Line - Solution

Link to the problem: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=654&page=show_problem&problem=152

The solution below used Brute Force to solve this problem.


import java.io.*;
import java.util.*;
import java.text.*;

class Main {
    public Coord[] coords; // keep coordinates of the computers
    public double minLength; // minimum length of cable
    public double totalLength; // keep the length of each attempt
    public int numComputers;
    public int[] considered;
    public Edge[] edges; // keep the edges used
    public Edge[] answer; // keep the best set of edges used
    public int index;
  
    public void rec(int x, int y, int numComputersConsidered) {
        if (totalLength > minLength) {
            return;
        }
      
        // if I considered all the computers
        if (numComputersConsidered == numComputers) {
            minLength = totalLength;
            for (int i = 0; i < numComputers-1; i++) {
                answer[i] = edges[i];
            }
        }
      
        for (int i = 0; i < numComputers; i++) { // try all the computer that I did not consider
            if (considered[i] == 1) {
                continue;
            }
            considered[i] = 1;
            double distance = Math.sqrt((x-coords[i].x)*(x-coords[i].x)+(y-coords[i].y)*(y-coords[i].y))+16;
            edges[index++] = new Edge(x, y, coords[i].x, coords[i].y, distance);
            totalLength += distance;
            rec(coords[i].x, coords[i].y, numComputersConsidered+1);
            index--;
            totalLength -= distance;
            considered[i] = 0;
        }
    }

    public void process() throws NumberFormatException, IOException {
        Scanner sc = new Scanner(System.in);
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
      
        int numCase = 0;
        numComputers = sc.nextInt();
        while (numComputers != 0) {
            coords = new Coord[numComputers];
            for (int i = 0; i < numComputers; i++) {
                int x = sc.nextInt();
                int y = sc.nextInt();
                coords[i] = new Coord(x, y);
            }
          
            minLength = Double.MAX_VALUE;
            considered = new int[numComputers];
            edges = new Edge[numComputers-1];
            answer = new Edge[numComputers-1];
            for (int i = 0; i < numComputers; i++) {
                index = 0;
                totalLength = 0;
                considered[i] = 1;
                rec(coords[i].x, coords[i].y, 1);
                considered[i] = 0;
            }
          
            DecimalFormat df = new DecimalFormat("#.00");
          
            bw.write("**********************************************************\n");
            bw.write("Network #" + ++numCase + "\n");
            for (int i = 0; i < numComputers-1; i++) {
                bw.write("Cable requirement to connect (" + answer[i].x1 + "," + answer[i].y1 + ") to (" + answer[i].x2 + "," + answer[i].y2 + ") is " + df.format(answer[i].dist) + " feet.\n");
            }
            bw.write("Number of feet of cable required is " + df.format(minLength) + ".\n");
                  
            numComputers = sc.nextInt();
        }
                                     
        bw.flush();
        bw.close();
      
        return;
    }
  
    public static void main(String[] args) throws NumberFormatException, IOException {
        Main m = new Main();
        m.process();
      
        System.exit(0);
    }
}

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

class Edge {
    int x1;
    int y1;
    int x2;
    int y2;
    double dist;
  
    public Edge(int x1, int y1, int x2, int y2, double dist) {
        this.x1 = x1;
        this.y1 = y1;
        this.x2 = x2;
        this.y2 = y2;
        this.dist = dist;
    }
}