Cod sursa(job #1276469)

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

class Punct implements Comparable<Punct> {

	int x,y;

	public Punct(int x, int y) {
		super();
		this.x = x;
		this.y = 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;
	}
	
	public int 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 int 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;
		int dist=Math.min(divide(s,m),divide(m+1,d));
		int 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;
		/*
		for(int i=s;i<m;i++)
		{
			if(p[i].distanta(p[m])<dist)
			{
				ps[ns++]= p[i];
			}
		}
		
		for(int i=m+1;i<=d;i++)
		{
			if(p[i].distanta(p[m])<dist)
			{
				pd[nd++]= p[i];
			}
		}
		for(int i=0;i<ns;i++)
			for(int j=0;j<nd;j++)
			{
				inter=Math.min(ps[i].distanta(pd[j]), inter);
			}
		*/
	}
	
	public static void main(String[] args) throws Exception
	{

			sc=new Scanner(new java.io.File("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);
			//System.out.println(Math.sqrt(divide(0,n-1)));
			
			iesire = new PrintWriter("cmap.out");
			iesire.printf("%.6f" , Math.sqrt(divide(0,n-1)));
			iesire.close();  
	}

}