/*
 * Auteur			: JM Vuong
 * Studie nummer	: 1263234
 * Datum			: 4 maart 2007
 */
import java.util.ArrayList;
import java.util.List;

public class Pair {
	private Point a;
	private Point b;
	private double distance;
	public Pair (Point a, Point b){
		this.a = a;
		this.b = b;
		this.distance = distance(a,b);
	}
	public Point get_point_a(){
		return a;
	}
	public Point get_point_b(){
		return b;
	}
	public double get_distance(){
		return this.distance;
	}
	public String toString(){
		return String.format("%s - %s distance %f", a,b,distance);
	}
	public static void main(String[] args){
		Point b = new Point(3,58,30);
		Point e = new Point(1000, 5, 300);
		Point c = new Point(2,31,100);
		Point a = new Point(1,22,1000);
		Point d = new Point(-1,3, 200);
		List<Point> t = new ArrayList<Point>();
		t.add(b);
		t.add(e);
		t.add(c);
		t.add(a);
		t.add(d);
		System.out.println("Algorithm says : "+find_closests(t));
		for(Point p : t)
			for (Point p2 : t)
				if (p != p2)
					System.out.println(new Pair(p,p2));
	}
	
	
	
	public static Pair find_closests (List<Point> in){
		return find_closest (Sort.sort_by_x(in), Sort.sort_by_y(in));
	}
	public static Pair find_closest( List<Point> sortedx, List<Point> sortedy ){
		if (sortedx.size() == 3){
			Pair a = new Pair(sortedx.get(0), sortedx.get(1));
			Pair b = new Pair(sortedx.get(0), sortedx.get(2));
			Pair c = new Pair(sortedx.get(1), sortedx.get(2));
			return min(a,min(b,c));
		}
		if (sortedx.size() == 2){
			Pair a = new Pair(sortedx.get(0), sortedx.get(1));
			return a;
		}
		if (sortedx.size() == 1 || sortedx.size() == 0){
			return null;
		}
		List<List<Point>> by_x = Sort.divide(sortedx);
		List<List<Point>> by_y = Sort.divide(sortedy);

		Pair a = find_closest (by_x.get(0), by_y.get(0));
		Pair b = find_closest (by_x.get(1), by_y.get(1));
		
		double mindistance = min(a,b).get_distance();
		int L = by_x.get(0).get(by_x.get(0).size() - 1).get_x(); // L
		
		ArrayList<Point> bla = new ArrayList<Point>();
		for(Point p : sortedy){
			if(p.get_x() > L - mindistance && p.get_x() < L + mindistance)
				bla.add(p);
		}
		
		Pair minp = minimum_pair (bla, null);
		
		if (minp instanceof Pair && minp.get_distance() < mindistance)
			return minp;
		else
			if (a.get_distance() < b.get_distance())
				return a;
			else
				return b;
		
	}
	public static Pair minimum_pair (List<Point> inlist, Pair minpair){
		if(inlist.isEmpty())
			return minpair;
		int count = 0;
		Point a = inlist.remove(0);
		while(count < 16){
			Point b;
			if(inlist.size() <= count)
				break;
			else
				b = inlist.get(count);
			count++;
			if(minpair != null)
				minpair = minpair.get_distance() < new Pair(a,b).get_distance() ? minpair : new Pair(a,b);
			else
				minpair = new Pair(a,b);
		}
		return minimum_pair (inlist, minpair);
	}
	public static double distance (Point a, Point b){
		double dx = Math.abs((double)a.get_x() - (double)b.get_x());
		double dy = Math.abs((double)a.get_y() - (double)b.get_y());
		return Math.sqrt(dx*dx + dy*dy);
	}
	public static Pair min (Pair a, Pair b){
		return a.get_distance() < b.get_distance() ? a : b; 
	}
}