Cod sursa(job #1275926)

Utilizator hellol30FMI Macovei Daniel hellol30 Data 25 noiembrie 2014 19:49:59
Problema Cele mai apropiate puncte din plan Scor 70
Compilator java Status done
Runda Arhiva educationala Marime 3.16 kb
//package DEI;

import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;
import java.io.PrintWriter;
import java.util.Arrays;

class Main {
    
    private static double dist(Punct p1, Punct p2) {
    
        return (p1.x - p2.x) * (p1.x - p2.x) + (p1.y - p2.y) * (p1.y - p2.y);
    }
    
    private static double divide(int st, int dr, Punct[] array) {
    
        if (dr - st <= 2) {
            return Math.min(Math.min(dist(array[st], array[st + 1]), dist(array[st], array[st + 2])), dist(array[st + 1], array[st + 2]));
        } else {
            int m = (st + dr) / 2;
            double d1 = Math.min(divide(st, m, array), divide(m, dr, array));
            double d2 = d1;
            for (int i = m; i >= st && array[m].x - array[i].x <= d1; i--)
                for (int j = 1; j <= 7 && i + j <= dr; j++)
                    d2 = Math.min(d2, dist(array[i], array[i + j]));
            return d2;
        }
    }
    
    public static void main(String args[]) throws IOException {
    
        //        for (int j = 0; j < 10; j++) {
        //            for (int i = 1; i <= 10; i++) {
        
        //                System.out.println("Doing test: " + i);
        //                long startTime = System.currentTimeMillis();
        int nrPuncte;
        Punct[] array = null;
        //                long operationStartTime = System.currentTimeMillis();
        BufferedReader br = new BufferedReader(new FileReader("cmap.in"));
        String line = null;
        nrPuncte = Integer.valueOf(br.readLine());
        array = new Punct[nrPuncte];
        Integer index = 0;
        while ((line = br.readLine()) != null) {
            double x = Double.valueOf(line.split(" ")[0]);
            double y = Double.valueOf(line.split(" ")[1]);
            array[index++] = new Punct(x, y);
        }
        //                System.out.println("Read in: " + (System.currentTimeMillis() - operationStartTime));
        //                operationStartTime = System.currentTimeMillis();
        Arrays.sort(array);
        //                System.out.println("Sort in: " + (System.currentTimeMillis() - operationStartTime));
        //                operationStartTime = System.currentTimeMillis();
        PrintWriter g = new PrintWriter("cmap.out");
        g.printf("%.6f\n", Math.sqrt(divide(0, nrPuncte - 1, array)));
        //                System.out.printf("%.6f\n", Math.sqrt(divide(0, nrPuncte - 1, array)));
        g.close();
        br.close();
        //                System.out.println("Solv in: " + (System.currentTimeMillis() - operationStartTime));
        //                System.out.println("Execution time: " + (System.currentTimeMillis() - startTime));
        //            }
        //        }
    }
}

class Punct implements Comparable<Punct> {
    double x, y;
    
    public Punct() {
    
        x = 0;
        y = 0;
    }
    
    public Punct(double x, double y) {
    
        this.x = x;
        this.y = y;
    }
    
    @Override
    public int compareTo(Punct a) {
    
        if (y < a.y)
            return -1;
        return 1;
    }
}