Cod sursa(job #1542036)

Utilizator Liviu0010Oprescu Liviu Liviu0010 Data 4 decembrie 2015 21:57:38
Problema Cele mai apropiate puncte din plan Scor 0
Compilator java Status done
Runda Arhiva educationala Marime 2.1 kb
import java.util.*;
import java.io.*;

class Main
{
	static Punct[] punct;
	
	static double getMin(int start, int end)
	{
		double minSt, minDr, minD;
		
		if(end - start <= 2)		//daca avem cel putin trei elemente
		{
			double[] mins = new double[end-start+1];
			double min = -1;
			int i, j=0;
			
			for(i = start; i <= end; i++)
				for(j = i+1; j<=end; j++)
					if(min == -1 || punct[i].distance(punct[j]) < min)
						min = punct[i].distance(punct[j]);
					
			return min;
		}
		
		minSt = getMin(start, (start+end)/2);
		minDr = getMin((start+end)/2+1, end);
		
		minD = minSt < minDr ? minSt : minDr;
		
		Punct[] db = new Punct[punct.length];
		int ndb = 0;
		
		for(int i = start; i <= end; i++)
			if(Math.abs(punct[i].x - punct[(start+end)/2].x) < minD)
				db[ndb++] = punct[i];
			
		Arrays.sort(db, 0, ndb, new Comparator<Punct>(){
			public int compare(Punct a, Punct b)
				{
					double d = a.y-b.y;
					if (d < 0)
						return -1;
					if(d > 0)
						return 1;
					return 0;
				}
		});
	
		for(int i = 0; i < ndb; i++)
			for(int j = i+1; j < ndb; j++)
				if(db[i].distance(db[j]) < minD)
					minD = db[i].distance(db[j]);
		
		return minD;
	}
	
	public static void main(String argsp[])
	{
		int n, a, b;
		
		try
		{
			Scanner sc = new Scanner(new File("cmap.in"));
			PrintWriter wr = new PrintWriter("cmap.out");
			n = sc.nextInt();
			
			punct = new Punct[n];
			
			for(int i = 0; i<n; i++)
				punct[i] = new Punct(sc.nextInt(), sc.nextInt());
			sc.close();
			
			Arrays.sort(punct, new Comparator<Punct>(){
				@Override
				public int compare(Punct a, Punct b)
				{
					if(a.x - b.x < 0)
						return -1;
					if(a.x - b.x > 0)
						return 1;
					return 0;
				}
			});
			
			wr.print(getMin(0, n-1));
			wr.close();
		}
		catch(IOException ioex)
		{
			System.out.println(ioex.getMessage());
		}
	}
}

class Punct
{
	double x, y;
	
	public Punct(double x, double y)
	{
		this.x = x;
		this.y = y;
	}
	
	public double distance(Punct p)
	{
		return Math.sqrt((x-p.x)*(x-p.x) + (y-p.y)*(y-p.y));
	}
}