Cod sursa(job #1267131)

Utilizator hellol30FMI Macovei Daniel hellol30 Data 19 noiembrie 2014 15:51:42
Problema Cele mai apropiate puncte din plan Scor 0
Compilator java Status done
Runda Arhiva educationala Marime 2.19 kb
import java.io.BufferedReader;
import java.io.FileReader;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.Scanner;

class Main {
	
	static Punct[] array = null, copy= null;
	
	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 Exception {
		
		    Scanner scanner = new Scanner(new BufferedReader(new FileReader("cmap.in")));
			int nrPuncte = scanner.nextInt();
			array = new Punct[nrPuncte];
			copy = 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("%.6f\n", Math.sqrt(divide(0, nrPuncte-1)));
			g.close();
			scanner.close();
	}
}
class Punct implements Comparable<Punct>{
	private int 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 int getX() {
		return x;
	}

	public void setX(int x) {
		this.x = x;
	}

	public int 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;
	}
}