rendered paste bodypackage 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);
}
}