Cod sursa(job #1275374)

Utilizator myshuSpatariu Mihai-Constantin myshu Data 25 noiembrie 2014 02:16:35
Problema Cele mai apropiate puncte din plan Scor 0
Compilator java Status done
Runda Arhiva educationala Marime 2.42 kb
import java.io.FileNotFoundException;
import java.util.*;

class customComparator implements Comparator<Punct>
{
    public int compare(Punct p1, Punct p2) 
	{
        return p1.inainte(p2);
    }
}

class Punct
{
	private double x;
	private double y;
	public void setX(double value)
	{
		x=value;
	}
	public void setY(double value)
	{
		y=value;
	}
	public double getX()
	{
		return x;
	}
	public double getY()
	{
		return y;
	}
	public Punct(double val1, double val2)
	{
		x=val1;
		y=val2;
	}
	public int inainte(Punct p)
	{
		if(x<p.getX()) return 1;
		else if(x==p.getX() && y<p.getY()) return 1;
		else return 0;
	}
	public double distanta(Punct p)
	{
		return Math.sqrt((p.getX()-x)*(p.getX()-x)+(p.getY()-y)*(p.getY()-y));
	}
}

class Apropiate
{
	static int n;
	static List<Punct> puncte = new ArrayList<Punct>();

	public static void main(String args[])
	{
		Apropiate t = new Apropiate();
		t.citire();
		t.sort();
		System.out.println(t.divide(0,n-1));
		
	}
	private double divide(int stg, int dr)
	{
		if(dr-stg > 2)
			{
				double min1 = divide(stg, (stg+dr)/2);
				double min2 = divide((stg+dr)/2+1,dr);
				if(min1>min2) 
					min1 = min2;
				int i = (stg+dr)/2;
				Punct p1,p2;
				p1 = new Punct(0,0);
				p2 = new Punct(0,0);
				while( i>=stg && puncte.get(i).getX() > (stg+dr)/2-min1)
					{
						p1 = puncte.get(i);
						int j = (stg+dr)/2 + 1;
						while(j<=dr && puncte.get(j).getX()<(stg+dr)/2 + min1)
						{
							p2 = puncte.get(j);
							if(p1.distanta(p2)< min1)
								min1 = p1.distanta(p2);
						    j++;
						}
						i--;
					}
				return min1;
			}
		else if(dr-stg == 1)
				return puncte.get(dr).distanta(puncte.get(stg));
			else 
				{
					double d = puncte.get(dr).distanta(puncte.get(stg));
					if(d > puncte.get(dr).distanta(puncte.get(stg+1)))
						d = puncte.get(dr).distanta(puncte.get(stg+1));
					if(d > puncte.get(dr-1).distanta(puncte.get(stg)))
						d = puncte.get(dr-1).distanta(puncte.get(stg));
					return d;
				}
		
	}
	private void citire()
	{
	try
	{
		Scanner fcin = new Scanner(new java.io.File("ex.in"));
		n=fcin.nextInt();
		for(int i=0;i<n;i++)
			puncte.add(new Punct(fcin.nextDouble(),fcin.nextDouble()));
	}
	catch(FileNotFoundException fnf)
		{
		System.out.println("Fisier inexistent");
		}
	}
	private void sort()
	{
		Collections.sort(puncte, new customComparator());
	}
}