Cod sursa(job #1276476)

Utilizator tudor.rotarusTudor Rotarus tudor.rotarus Data 26 noiembrie 2014 14:34:50
Problema Cele mai apropiate puncte din plan Scor 40
Compilator java Status done
Runda Arhiva educationala Marime 1.57 kb
import java.io.*;
import java.util.*;

class Punct implements Comparable<Punct> {

	double x,y;

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

	public double getX() {
		return x;
	}

	public double getY() {
		return y;
	}
	
	public double distanta(Punct a)
	{
		return (x-a.getX())*(x-a.getX())+(y-a.getY())*(y-a.getY());
	}

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

	static Scanner sc;
	static Punct[] p;
	static PrintWriter iesire;

	
	public static double divide(int s,int d)
	{
		if(d-s<=2)
		{
			if(d-s==2)
				return Math.min(Math.min(p[s].distanta(p[s+1]), p[s].distanta(p[s+1])), p[s+1].distanta(p[s+2]));
			else return Math.min(p[s].distanta(p[s+1]), p[s].distanta(p[s+1]));
		}
		int m= (s+d)/2;
		double dist=Math.min(divide(s,m),divide(m+1,d));
		double inter=dist;
		for (int i = m; i >= s && p[m].getX() - p[i].getX() <= dist; i--)
            for (int j = 1; j <= 7 && i + j <= d; j++)
                inter = Math.min(inter, p[i].distanta(p[i + j]));
        return inter;
		
	}
	
	public static void main(String[] args) throws Exception
	{

			sc=new Scanner(new FileInputStream("cmap.in"));
			int n = sc.nextInt();
			p = new Punct[n];
			for(int i=0;i<n;i++)
			{
				int x = sc.nextInt();
				int y = sc.nextInt();
				p[i] = new Punct(x,y);
			}
			Arrays.sort(p);
			
			iesire = new PrintWriter("cmap.out");
			iesire.printf("%.6f" , Math.sqrt(divide(0,n-1)));
			iesire.close();  
	}

}