Cod sursa(job #1542871)

Utilizator Liviu0010Oprescu Liviu Liviu0010 Data 5 decembrie 2015 19:03:57
Problema Cele mai apropiate puncte din plan Scor 100
Compilator java Status done
Runda Arhiva educationala Marime 2.93 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];
			
			for(i = start; i < end; i++)
			{
				int _min = i;
				Punct aux;
				
				for(j = i+1; j <= end; j++)
					if(ySorted[j].y < ySorted[_min].y)
						_min = j;
				
				if(_min != i)
				{
					aux = ySorted[i];
					ySorted[i] = ySorted[_min];
					ySorted[_min] = aux;
				}
			}
			
			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
		{
			BufferedReader br = new BufferedReader(new FileReader("cmap.in"));
			StringTokenizer stok;
			
			FileOutputStream fos = new FileOutputStream("cmap.out");
			PrintWriter wr = new PrintWriter((OutputStream)fos);
			Punct[] s;
			
			n = Integer.parseInt(br.readLine());
			
			punct = new Punct[n];
			s = new Punct[n];
			
			for(int i = 0; i<n; i++)
			{
				stok = new StringTokenizer(br.readLine());
				punct[i] = new Punct(Long.parseLong(stok.nextToken()), Long.parseLong(stok.nextToken()));
			}
			br.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);
	}
}