(SPOJ) Cubra os furos - Solution

Link to the problem: http://br.spoj.com/problems/FUROS/

The solution below calculates the distance between every pair of holes. For every distance calculated, we keep the maximum distance. Then, we keep the minimum distance among the maximum distances.


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

class solucao {
    public static int reader(BufferedReader br) throws NumberFormatException, IOException {     
        int n;
        int resp = 0;     
        int sinal = 1;     
      
        while (true) {         
            n = br.read();         
            if (n >= '0' && n <= '9') {
                break;
            }
            if (n == '-') {
                sinal = -1;
            }         
            if (n == '+') {
                sinal = 1;
            }    
        }
           
        while (true) {         
            resp = resp*10 + n-'0';         
            n = br.read();         
            if (n < '0' || n > '9') {
                break;     
            }
        }
      
        return resp*sinal;     
    }
   
    public void process() throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
       
        int numTest = 0;
        int numHoles = reader(br);
       
        while (numHoles != 0) {
            Coord[] coords = new Coord[numHoles];
            for (int i = 0; i < numHoles; i++) {
                int x = reader(br);
                int y = reader(br);
                coords[i] = new Coord(x, y);
            }

            // calculate the distance between every pair of holes           
            double minDistance = Double.MAX_VALUE;
            for (int i = 0; i < numHoles; i++) {
                double maxDistance = 0;
                for (int j = 0; j < numHoles; j++) {
                    double distance = (coords[i].x-coords[j].x)*(coords[i].x-coords[j].x)+(coords[i].y-coords[j].y)*(coords[i].y-coords[j].y);
                    // keep the maximum distance between the hole i and j
                    maxDistance = Math.max(maxDistance, distance);
                }
                // keep the minimum distance among the maximum distances
                minDistance = Math.min(minDistance, maxDistance);
            }
           
            bw.write("Teste " + ++numTest + "\n");
            bw.write((int)Math.ceil((Math.sqrt(minDistance)+2.5)*2)+"\n\n");
       
            numHoles = reader(br);
        }
                   
        bw.flush();
        bw.close();
       
        return;
    }
   
    public static void main(String[] args) throws NumberFormatException, IOException {
        solucao m = new solucao();
        m.process();
       
        System.exit(0);
    }
}

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