Cod sursa(job #1542151)

Utilizator Liviu0010Oprescu Liviu Liviu0010 Data 5 decembrie 2015 01:22:47
Problema Cele mai apropiate puncte din plan Scor 50
Compilator java Status done
Runda Arhiva educationala Marime 2.77 kb
import java.util.*;
import java.io.*;

class Main
{
	static Punct[] punct;
	
	static long getMin(int start, int end, Punct[] ySorted)
	{
		long minSt, minDr, minD;
		
		if(end - start <= 2)		//daca avem cel putin trei elemente
		{
			long 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]);
			
			for(i = start; i <= end; i++)
				ySorted[i] = punct[i];
			
			Arrays.sort(ySorted, start, end+1,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;
				}
			});
			
			return min;
		}
		
		Punct[] tmp = new Punct[end-start+1];
		
		minSt = getMin(start, (start+end)/2, ySorted);
		minDr = getMin((start+end)/2+1, end, ySorted);
		minD = minSt < minDr ? minSt : minDr;
		
		int nTmp = 0, a=start, b=(start+end)/2+1;
		
		while(a <= (start+end)/2 && b <= end)
			if(ySorted[a].y < ySorted[b].y)
				tmp[nTmp++] = ySorted[a++];
			else
				tmp[nTmp++] = ySorted[b++];
		
		while(a <= (start+end)/2)
			tmp[nTmp++] = ySorted[a++];
		
		while(b <= end)
			tmp[nTmp++] = ySorted[b++];
		
		for(int i = start; i <= end; i++)
			ySorted[i] = tmp[i-start];
		
		Punct[] db = new Punct[tmp.length];
		int ndb = 0;
		
		for(int i = 0; i < tmp.length; i++)
			if(Math.abs(tmp[i].x - punct[(start+end)/2].x) < minD)
				db[ndb++] = tmp[i];
			
		for(int i = 0; i < ndb; i++)
			for(int j = i+1; j < ndb && j <= i+7; j++)
					if(db[i].distance(db[j]) < minD)
						minD = db[i].distance(db[j]);
		
		return minD;
	}
	
	public static void main(String argsp[])
	{
		int n;
		
		try
		{
			FileInputStream fis = new FileInputStream("cmap.in");
			Scanner sc = new Scanner((InputStream)fis);
			
			FileOutputStream fos = new FileOutputStream("cmap.out");
			PrintWriter wr = new PrintWriter((OutputStream)fos);
			Punct[] s;
			
			n = sc.nextInt();
			
			punct = new Punct[n];
			s = new Punct[n];
			
			for(int i = 0; i<n; i++)
				punct[i] = new Punct(sc.nextLong(), sc.nextLong());
			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(Math.sqrt(getMin(0, n-1, s)));
			wr.close();
				
		}
		catch(IOException ioex)
		{
			System.out.println(ioex.getMessage());
		}
	}
}

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