Cod sursa(job #1275624)

Utilizator hellol30FMI Macovei Daniel hellol30 Data 25 noiembrie 2014 13:51:14
Problema Cele mai apropiate puncte din plan Scor 0
Compilator java Status done
Runda Arhiva educationala Marime 2.8 kb
package DEI;

import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.Scanner;

class DEI11 {
    
    static Punct[] array = null, copy = null, aux = null;
    static int nrPuncte;
    
    private static double dist(Punct p1, Punct p2) {
    
        return (p1.getX() - p2.getX()) * (p1.getX() - p2.getX()) + (p1.getY() - p2.getY()) * (p1.getY() - p2.getY());
    }
    
    private static double divide(int st, int dr) {
    
        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), divide(m, dr));
            double d2 = d1;
            for (int i = m; i >= st && array[m].getX() - array[i].getX() <= 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 FileNotFoundException {
    
        Scanner scanner = new Scanner(new FileReader("cmap.in"));
        nrPuncte = scanner.nextInt();
        array = new Punct[nrPuncte];
        copy = new Punct[nrPuncte];
        aux = new Punct[nrPuncte];
        
        for (int index = 0; index < nrPuncte; index++) {
            
            int x = scanner.nextInt();
            int y = scanner.nextInt();
            array[index] = new Punct(x, y);
        }
        Arrays.sort(array);
        for (int index = 0; index < nrPuncte; index++)
            copy[index] = new Punct(array[index].getX(), array[index].getY());
        PrintWriter g = new PrintWriter("cmap.out");
        g.printf("%.8f\n", Math.sqrt(divide(0, nrPuncte - 1)));
        g.close();
        scanner.close();
    }
}

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