package Exercise4;

public class Pair
{
	private Point p1;
	private Point p2;
	private float distance;
	private float distance3d;

	public Pair(Point _p1, Point _p2)
	{
		p1 = _p1;
		p2 = _p2;
		float x_dist = (p1.getX() - p2.getX());
		float y_dist = (p1.getY() - p2.getY());
		float z_dist = (p1.getZ() - p2.getZ());
		distance = (float)Math.sqrt((x_dist*x_dist) + (y_dist*y_dist));
		distance3d = (float)Math.sqrt((x_dist*x_dist) + (y_dist*y_dist) + (z_dist*z_dist));
	}

	public float getDistance()
	{
		return distance;
	}

	public float get3DDistance()
	{
		return distance3d;
	}

	public Point getPoint1()
	{
		return p1;
	}

	public Point getPoint2()
	{
		return p2;
	}

	public String toString()
	{
		return "" + p1 + " " + p2 + "";
	}
}


package Exercise4;

public class Exercise
{
	public static int filterOn(int axis, Point[] fspo, Point spi[], float left, float right)
	{
		int length = 0;

		for(int i = 0; i < spi.length; i++)
		{
			if(left < spi[i].get(axis) && spi[i].get(axis) < right)
			{
				fspo[length] = spi[i];
				length++;
			}
		}
		return length;

	}

	public static Point[] mergesort(Point p[], int lower, int upper, int axis)
	{
		Point ret[] = new Point[upper-lower+1];

		if((upper - lower) == 0)
		{
			ret[0] = p[lower];
			return ret;
		}
		if((upper - lower) == 1)
		{
			//this is where we have to sort
			if(p[lower].get(axis) > p[upper].get(axis))
			{
				ret[0] = p[upper];
				ret[1] = p[lower];
			}else{
				ret[0] = p[lower];
				ret[1] = p[upper];
			}			
			return ret;
		}
		int middle = (upper+lower)/2;
		Point right[] = mergesort(p, middle+1, upper, axis);
		Point left[] = mergesort(p, lower, middle, axis);

		int l = 0,r = 0;
		for(int i = 0; i < p.length; i++)
		{
			if((l < left.length) && (r < right.length))
			{
				if(right[r].get(axis) < left[l].get(axis))
				{
					ret[i] = right[r];
					r++;
				}else{
					ret[i] = left[l];
					l++;
				}
			}else{
				if(l < left.length)
				{
					ret[i] = left[l];
					l++;
				}else if(r < right.length){
					ret[i] = right[r];
					r++;
				}
			}
		}
		return ret;
	}

	public static Pair closestpair(Point spx[], Point spy[], int lower, int upper)
	{
		if((upper - lower) < 3) //3 points or less left
		{
			if(lower==upper) //we have a problem
				return null;
			Pair min = new Pair(spx[lower], spx[upper]);
			if((lower-upper) > 1)
			{
				Pair p1 = new Pair(spx[lower], spx[lower+1]);
				Pair p2 = new Pair(spx[upper-1], spx[upper]);
				if(p2.getDistance() < p1.getDistance())
				{
					p1 = p2;
				}

				if(p1.getDistance() < min.getDistance())
				{
					min = p1;
				}
			}
			return min;
		}

		int middle = (upper + lower) / 2;

		Pair l = closestpair(spx, spy, lower, middle);
		Pair r = closestpair(spx, spy, middle + 1, upper);
		Pair min;
		
		if(l.getDistance() < r.getDistance())
			min = l;
		else
			min = r;
				
		Point fpy[] = new Point[spy.length];
		int length = filterOn(Point.X, fpy, spy, (float)(spx[(middle + 1)].getX()) - min.getDistance(), (float)(spx[middle].getX()) + min.getDistance());
		
		for(int i = 0; i < length;i++)
		{
			for(int j = 1; j <= 3; j++) //The reason I look 6 nodes around this one is explained in the documentation
			{
				if(i+j < length)
				{
					Pair p = new Pair(fpy[i], fpy[i+j]);
					if(p.getDistance() < min.getDistance())
						min = p;
				}

				if(i-j > 0)			
				{
					Pair p = new Pair(fpy[i-j], fpy[i]);
					if(p.getDistance() < min.getDistance())
					{
						min = p;
					}
				}
			}
		}

		return min;

	}

	public static Pair closestpair3d(Point spx[], Point spy[], Point spz[], int lower, int upper)
	{
		if((upper - lower) < 3) //3 points or less left
		{
			if(lower==upper) //we have a problem
				return null;
				Pair min = new Pair(spz[lower], spz[upper]);
			if((lower-upper) > 1)
			{
				Pair p1 = new Pair(spz[lower], spz[lower+1]);
				Pair p2 = new Pair(spz[upper-1], spz[upper]);
				if(p2.get3DDistance() < p1.get3DDistance())
				{
					p1 = p2;
				}

				if(p1.get3DDistance() < min.get3DDistance())
				{
					min = p1;
				}
			}
			return min;
		}

		int middle = (upper + lower) / 2;

		Pair l = closestpair3d(spx, spy, spz, lower, middle);
		Pair r = closestpair3d(spx, spy, spz, middle + 1, upper);
		Pair min;
		
		if(l.getDistance() < r.getDistance())
			min = l;
		else
			min = r;
				
		Point fspx[] = new Point[spx.length];
		int length = filterOn(Point.Z, fspx, spx, (float)(spz[(middle + 1)].getZ()) - min.get3DDistance(), (float)(spz[middle].getZ()) + min.get3DDistance());
		if(length > 0)
		{
			Pair min2d = closestpair(spx,spy,0, length-1);

			if(min2d.get3DDistance() < min.get3DDistance())
				min = min2d;
		}
		return min;
	}


	public static void main(String args[])
	{
		Point p[] = DataReader.getData(args[0]);

		Point spx[] = mergesort(p, 0, p.length - 1, Point.X);
		Point spy[] = mergesort(p, 0, p.length - 1, Point.Y);
		Point spz[] = mergesort(p, 0, p.length - 1, Point.Z);

		Pair cp2d = closestpair(spx, spy, 0, p.length - 1);
		
		if(cp2d.getPoint1().get(Point.AI) > cp2d.getPoint2().get(Point.AI))
			cp2d = new Pair(cp2d.getPoint2(), cp2d.getPoint1());
		
		System.out.println("" + cp2d);


		Pair cp3d = closestpair3d(spx, spy, spz, 0, p.length - 1);
		
		if(cp3d.getPoint1().get(Point.AI) > cp3d.getPoint2().get(Point.AI))
			cp3d = new Pair(cp3d.getPoint2(), cp3d.getPoint1());

		System.out.println("bonus: " + cp3d);


	}
}



package Exercise4;

import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
public class DataReader {
	public static Point[] getData(String fileName)
	{
		try{
			BufferedReader bi = new BufferedReader(new FileReader(new File(fileName)));
			int amount = Integer.parseInt( (bi.readLine()).split(" ")[0]);
			Point ret[] = new Point[amount];


			for(int i=0;i<amount;i++)
			{
				String temp = bi.readLine();
				String token[] = temp.split(" ");

				ret[i] = new Point(i, token[0], Integer.parseInt(token[1]), Integer.parseInt(token[2]), Integer.parseInt(token[3]));
			}
			return ret;
	
		}catch(Exception e)
		{
			System.out.println("Exception caught: " + e.getMessage());
		}
		return null;
	}

}


package Exercise4;

public class Exercise
{
	public static int filterOn(int axis, Point[] fspo, Point spi[], float left, float right)
	{
		int length = 0;

		for(int i = 0; i < spi.length; i++)
		{
			if(left < spi[i].get(axis) && spi[i].get(axis) < right)
			{
				fspo[length] = spi[i];
				length++;
			}
		}
		return length;

	}

	public static Point[] mergesort(Point p[], int lower, int upper, int axis)
	{
		Point ret[] = new Point[upper-lower+1];

		if((upper - lower) == 0)
		{
			ret[0] = p[lower];
			return ret;
		}
		if((upper - lower) == 1)
		{
			//this is where we have to sort
			if(p[lower].get(axis) > p[upper].get(axis))
			{
				ret[0] = p[upper];
				ret[1] = p[lower];
			}else{
				ret[0] = p[lower];
				ret[1] = p[upper];
			}			
			return ret;
		}
		int middle = (upper+lower)/2;
		Point right[] = mergesort(p, middle+1, upper, axis);
		Point left[] = mergesort(p, lower, middle, axis);

		int l = 0,r = 0;
		for(int i = 0; i < p.length; i++)
		{
			if((l < left.length) && (r < right.length))
			{
				if(right[r].get(axis) < left[l].get(axis))
				{
					ret[i] = right[r];
					r++;
				}else{
					ret[i] = left[l];
					l++;
				}
			}else{
				if(l < left.length)
				{
					ret[i] = left[l];
					l++;
				}else if(r < right.length){
					ret[i] = right[r];
					r++;
				}
			}
		}
		return ret;
	}

	public static Pair closestpair(Point spx[], Point spy[], int lower, int upper)
	{
		if((upper - lower) < 3) //3 points or less left
		{
			if(lower==upper) //we have a problem
				return null;
			Pair min = new Pair(spx[lower], spx[upper]);
			if((lower-upper) > 1)
			{
				Pair p1 = new Pair(spx[lower], spx[lower+1]);
				Pair p2 = new Pair(spx[upper-1], spx[upper]);
				if(p2.getDistance() < p1.getDistance())
				{
					p1 = p2;
				}

				if(p1.getDistance() < min.getDistance())
				{
					min = p1;
				}
			}
			return min;
		}

		int middle = (upper + lower) / 2;

		Pair l = closestpair(spx, spy, lower, middle);
		Pair r = closestpair(spx, spy, middle + 1, upper);
		Pair min;
		
		if(l.getDistance() < r.getDistance())
			min = l;
		else
			min = r;
				
		Point fpy[] = new Point[spy.length];
		int length = filterOn(Point.X, fpy, spy, (float)(spx[(middle + 1)].getX()) - min.getDistance(), (float)(spx[middle].getX()) + min.getDistance());
		
		for(int i = 0; i < length;i++)
		{
			for(int j = 1; j <= 3; j++) //The reason I look 6 nodes around this one is explained in the documentation
			{
				if(i+j < length)
				{
					Pair p = new Pair(fpy[i], fpy[i+j]);
					if(p.getDistance() < min.getDistance())
						min = p;
				}

				if(i-j > 0)			
				{
					Pair p = new Pair(fpy[i-j], fpy[i]);
					if(p.getDistance() < min.getDistance())
					{
						min = p;
					}
				}
			}
		}

		return min;

	}

	public static Pair closestpair3d(Point spx[], Point spy[], Point spz[], int lower, int upper)
	{
		if((upper - lower) < 3) //3 points or less left
		{
			if(lower==upper) //we have a problem
				return null;
				Pair min = new Pair(spz[lower], spz[upper]);
			if((lower-upper) > 1)
			{
				Pair p1 = new Pair(spz[lower], spz[lower+1]);
				Pair p2 = new Pair(spz[upper-1], spz[upper]);
				if(p2.get3DDistance() < p1.get3DDistance())
				{
					p1 = p2;
				}

				if(p1.get3DDistance() < min.get3DDistance())
				{
					min = p1;
				}
			}
			return min;
		}

		int middle = (upper + lower) / 2;

		Pair l = closestpair3d(spx, spy, spz, lower, middle);
		Pair r = closestpair3d(spx, spy, spz, middle + 1, upper);
		Pair min;
		
		if(l.getDistance() < r.getDistance())
			min = l;
		else
			min = r;
				
		Point fspx[] = new Point[spx.length];
		int length = filterOn(Point.Z, fspx, spx, (float)(spz[(middle + 1)].getZ()) - min.get3DDistance(), (float)(spz[middle].getZ()) + min.get3DDistance());
		if(length > 0)
		{
			Pair min2d = closestpair(spx,spy,0, length-1);

			if(min2d.get3DDistance() < min.get3DDistance())
				min = min2d;
		}
		return min;
	}


	public static void main(String args[])
	{
		Point p[] = DataReader.getData(args[0]);

		Point spx[] = mergesort(p, 0, p.length - 1, Point.X);
		Point spy[] = mergesort(p, 0, p.length - 1, Point.Y);
		Point spz[] = mergesort(p, 0, p.length - 1, Point.Z);

		Pair cp2d = closestpair(spx, spy, 0, p.length - 1);
		
		if(cp2d.getPoint1().get(Point.AI) > cp2d.getPoint2().get(Point.AI))
			cp2d = new Pair(cp2d.getPoint2(), cp2d.getPoint1());
		
		System.out.println("" + cp2d);


		Pair cp3d = closestpair3d(spx, spy, spz, 0, p.length - 1);
		
		if(cp3d.getPoint1().get(Point.AI) > cp3d.getPoint2().get(Point.AI))
			cp3d = new Pair(cp3d.getPoint2(), cp3d.getPoint1());

		System.out.println("bonus: " + cp3d);


	}
}