Mai intai trebuie sa te autentifici.

Cod sursa(job #1279968)

Utilizator TwoOfDiamondsDaniel Alexandru Radu TwoOfDiamonds Data 1 decembrie 2014 11:20:29
Problema Cele mai apropiate puncte din plan Scor 0
Compilator java Status done
Runda Arhiva educationala Marime 3.76 kb
import java.util.Scanner;
import java.io.*;
import java.util.ArrayList;
import java.util.Collections;

class Point
{
	public int x, y;
	public int px, py;
}

class DistMin
{
	public static void main(String[] args)
	{
		ArrayList<Point> puncteX = new ArrayList<Point>();
		ArrayList<Point> puncteY = new ArrayList<Point>();
		try
		{
			Scanner sc = new Scanner(new java.io.File("cmap.in"));
			
			int n;
			n = sc.nextInt();
			
			//puncte = new Point[n];
			
			for(int i = 0; i < n; i++)
			{
				Point p = new Point();
				p.x = sc.nextInt();
				p.y = sc.nextInt();
				puncteX.add(p);
				puncteY.add(p);
			}
			
			sc.close();
			
			//apel catre functia de det
			//Collections.sort(puncteX, (Point a, Point b)->
			//{
			//	return a.x - b.x;
			//});
			Collections.sort(puncteX, new Comparator<Point>(){
				public int compare(Point a, Point b){
					return a.x - b.x;
				}});
			//Collections.sort(puncteY, (Point a, Point b)->
			//{
			//	return a.y - b.y;
			//});
			
			Collections.sort(puncteY, new Comparator<Point>(){
				public int compare(Point a, Point b){
					return a.y - b.y;
					}});
			
			for(int i = 0; i < puncteX.size(); i++)
			{
				puncteX.get(i).py = Collections.binarySearch(puncteY, puncteX.get(i), (Point a, Point b) ->
				{
					return a.y - b.y;
				});
				
				puncteY.get(puncteX.get(i).py).px = i;
			}
			
			PrintWriter pw = new PrintWriter(new FileWriter(new File("cmap.out")));
			
			pw.println(dist(puncteX, puncteY , 0, puncteX.size()));
			//for(int i = 0; i < n; i++)
			//{
			//	pw.println(puncte.get(i).x + " " +puncte.get(i).y);
			//}
			
			pw.close();
		}
		
		catch(Exception ex)
		{
			System.out.println("404");
		}
	}
	
	static double getdistance(Point a, Point b)
	{
		double x = a.x - b.x;
		x *= x;
		double y = a.y - b.y;
		y *= y;
		return Math.sqrt(x + y);
	}
	
	static double dist(ArrayList<Point> puncteX, ArrayList<Point> puncteY, int beg, int end)
	{
		if(end - beg < 2)
			return Double.MAX_VALUE;
		if(end - beg <= 3)
		{
			double min;
			double alpha = getdistance(puncteX.get(beg), puncteX.get(beg+1));
			if(end - beg == 3)
			{
				double beta = getdistance(puncteX.get(beg), puncteX.get(beg+2));
				double theta = getdistance(puncteX.get(beg+1), puncteX.get(beg+2));
				min = alpha < beta ? alpha : beta;
				min = theta < min ? theta : min;
			}
			else
				min = alpha;
			return min;
		}
		
		int linie = beg + (end - beg) / 2;
		double d1 = dist(puncteX, puncteY, beg, linie);
		double d2 = dist(puncteX, puncteY, linie, end);
		double min = d1 < d2 ? d1 : d2;
		double d3 = getd3(puncteX, puncteY, beg, end, linie, min);
		
		return d3 < min ? d3 : min;
		
	}
	
	static double getd3(ArrayList<Point> puncteX, ArrayList<Point> puncteY, int beg, int end, int linie, double min)
	{
		ArrayList<Point> banda = new ArrayList<Point>();
		ArrayList<Point> bandaY = new ArrayList<Point>();
		boolean[] shouldadd = new boolean[puncteX.size()];
		
		int pozlinie = puncteX.get(linie).x;
		
		for(int i = beg; i < end; i++)
		{
			shouldadd[puncteX.get(i).py] = false;
			double distLine = puncteX.get(i).x - pozlinie;
			if(distLine < 0)
				distLine *= -1;
			if(distLine <= min)
			{
				banda.add(puncteX.get(i));
				shouldadd[puncteX.get(i).py] = true;
			}
		}
		
		for(int i = 0; i < puncteX.size(); i++)
		{
			if(shouldadd[i])
			{
				bandaY.add(puncteY.get(i));
			}
			
		}
		
		for(int i = 0; i < bandaY.size(); i++)
		{
			int limit = 15 < bandaY.size() - i - 1 ? 15 : bandaY.size() - i - 1;
			
			for(int j = 1; j <= limit; j++)
			{
				double dist = getdistance(bandaY.get(i), bandaY.get(i+j));
				if(dist < min)
				{
					min = dist;
				}
			}
			
		}
		
		return min;
	}
}