Cod sursa(job #1276614)

Utilizator hellol30FMI Macovei Daniel hellol30 Data 26 noiembrie 2014 17:13:30
Problema Cele mai apropiate puncte din plan Scor 60
Compilator java Status done
Runda Arhiva educationala Marime 3.47 kb
//package cmap;

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

class Main {

	static double dist(Punct A, Punct B){
		return ( B.x - A.x ) * ( B.x - A.x ) + ( B.y - A.y ) * ( B.y - A.y );
	}
	
	static void merge( int st, int dr, Punct[] aux, Punct[] array ){
		
	    int mid = (st + dr) / 2, p1 = st, p2 = mid + 1, len = 0;
	     
	    while (p1 <= mid || p2 <= dr)
	        if (p1 > mid) 
	            aux[++len] = array[p2++];
	        else if (p2 > dr)
	            aux[++len] = array[p1++];
	        else if (array[p1].x < array[p2].x)
	            aux[++len] = array[p1++];
	        else
	            aux[++len] = array[p2++];
	     
	    for (int i = st, j = 1; i <= dr; ++i, ++j)
	        array[i] = aux[j];
	}
	
	static double divide(int st, int dr, Punct[] aux, Punct[] array, Punct[] copyOfSortedArray){
		
		double res = Double.MAX_VALUE;
	    if (dr - st <= 2) {
	        for (int i = st; i <= dr; ++i)
	            for (int j = i + 1; j <= dr; ++j)
	                res = Math.min(res, dist(array[i], array[j]));
	        Arrays.sort(array, st, dr+1);
	        return res;
	    }
	     
	    int mid = (st + dr) / 2;
	    res = Math.min(divide(st, mid, aux, array, copyOfSortedArray), divide(mid + 1, dr, aux, array,copyOfSortedArray));
	     
	    merge(st, dr, aux, array);
	     
	    int len = 0;
	    for (int i = st; i <= dr; ++i)
	        if (Math.abs(array[i].x - copyOfSortedArray[mid].x) <= res)
	            aux[++len] = array[i];
	     
	    for (int i = 1; i < len; ++i)
	        for (int j = i + 1, cnt = 1; cnt <= 7 && j < aux.length; ++j, ++cnt)
	            res = Math.min(res, dist(aux[i], aux[j]));
	     
	    return res;
	}
	
	public static void main(String args[]) throws NumberFormatException, IOException{

		int nrPuncte;
		Punct[] array = null;
		Punct[] copyOfSortedArray = null;
		Punct[] aux = null;
		
		
	   BufferedReader br = new BufferedReader(new FileReader("cmap.in"));
	   
	   nrPuncte = Integer.valueOf(br.readLine());
	   array = new Punct[nrPuncte+1];
	   aux = new Punct[nrPuncte+1];
	   copyOfSortedArray = new Punct[nrPuncte+1];
	   String line = null;
	   for (int index = 1 ; (line = br.readLine()) != null; index++) {
		   double x = Integer.valueOf(line.split(" ")[0]);
	       double y = Integer.valueOf(line.split(" ")[1]);
	       array[index] = new Punct(x, y);
	       aux[index] = new Punct();
	   }
	   br.close();
	   Arrays.sort(array,1,nrPuncte, new Comparator<Punct>() {

			@Override
			public int compare(Punct o1, Punct o2) {
				if(o1.x < o2.x)
					return -1;
				if(o1.x > o2.x)
					return 1;
				if(o1.x < o2.x)
					return -1;
				if(o1.y > o2.y)
					return 1;
				return 0;
			}
		});
		     
		for(int index = 1; index <= nrPuncte;index++ ){
		    copyOfSortedArray[index] = new Punct(array[index].x, array[index].y);
		}
		     
		PrintWriter printer = new PrintWriter("cmap.out");
		printer.printf("%.6f\n", Math.sqrt(divide(1, nrPuncte, aux, array, copyOfSortedArray)));
		printer.close();
	}
}
class Punct implements Comparable<Punct>{
	double x,y;

	public Punct(double x, double y) {
		this.x = x;
		this.y = y;
	}

	public Punct() {
		x=0;
		y=0;
	}

	@Override
	public int compareTo(Punct o) {
		if(y < o.y)
			return -1;
		if(y > o.y)
			return 1;
		return 0;
	}
}