NEERC/asteroids/asteroids_mb.java

   1 import java.io.*;
   2 import java.util.*;
   3
   4 public class asteroids_mb implements Runnable {
   5     private static final double EPSILON = 1e-6;
   6
   7     static class Point3d {
   8         public final double x;
   9         public final double y;
  10         public final double z;
  11
  12         public Point3d(double x, double y, double z) {
  13             this.x = x;
  14             this.y = y;
  15             this.z = z;
  16         }
  17
  18         public static Point3d read(Scanner in) {
  19             final int x = in.nextInt();
  20             final int y = in.nextInt();
  21             final int z = in.nextInt();
  22             return new Point3d(x, y, z);
  23         }
  24     }
  25
  26     static class Plane3d implements Comparable<Plane3d> {
  27         public double a;
  28         public double b;
  29         public double c;
  30         public double d;
  31
  32         public Plane3d(Point3d p1, Point3d p2, Point3d p3) {
  33             a = (p2.y - p1.y) * (p3.z - p1.z) - (p3.y - p1.y) * (p2.z - p1.z);
  34             b = (p2.z - p1.z) * (p3.x - p1.x) - (p3.z - p1.z) * (p2.x - p1.x);
  35             c = (p2.x - p1.x) * (p3.y - p1.y) - (p3.x - p1.x) * (p2.y - p1.y);
  36             d = -(a * p1.x + b * p1.y + c * p1.z);
  37             final double norm = Math.sqrt(a * a + b * b + c * c);
  38             a /= norm;
  39             b /= norm;
  40             c /= norm;
  41             d /= norm;
  42
  43             if (a < 0 || Math.abs(a) < EPSILON && b < 0 || Math.abs(a) < EPSILON && Math.abs(b) < EPSILON && c < 0) {
  44                 a = -a;
  45                 b = -b;
  46                 c = -c;
  47                 d = -d;
  48             }
  49         }
  50
  51         public double getDist(Point3d origin) {
  52             return a * origin.x + b * origin.y + c * origin.z + d;
  53         }
  54
  55         public int compareTo(Plane3d o) {
  56             if (a < o.a - EPSILON) {
  57                 return -1;
  58             }
  59             if (a > o.a + EPSILON) {
  60                 return +1;
  61             }
  62             if (b < o.b - EPSILON) {
  63                 return -1;
  64             }
  65             if (b > o.b + EPSILON) {
  66                 return +1;
  67             }
  68             if (c < o.c - EPSILON) {
  69                 return -1;
  70             }
  71             if (c > o.c + EPSILON) {
  72                 return +1;
  73             }
  74             if (d < o.d - EPSILON) {
  75                 return -1;
  76             }
  77             if (d > o.d + EPSILON) {
  78                 return +1;
  79             }
  80             return 0;
  81         }
  82     }
  83
  84     static class Face {
  85         public final Plane3d p;
  86         public final Point3d[] v;
  87
  88         public Face(Plane3d p, Point3d[] v) {
  89             this.p = p;
  90             this.v = v;
  91         }
  92     }
  93
  94     static class Polyhedron {
  95         private final Point3d[] vertices;
  96
  97         public Polyhedron(Point3d[] vertices) {
  98             this.vertices = vertices;
  99         }
 100
 101         public static Polyhedron read(Scanner in) {
 102             final int n = in.nextInt();
 103             Point3d[] vertices = new Point3d[n];
 104             for (int i = 0; i < n; i++) {
 105                 vertices[i] = Point3d.read(in);
 106             }
 107             return new Polyhedron(vertices);
 108         }
 109
 110         public double getDist() {
 111             ArrayList<Face> faces = new ArrayList<Face>();
 112             TreeSet<Plane3d> facePlanes = new TreeSet<Plane3d>();
 113             for (int i = 0; i < vertices.length; i++) {
 114                 Point3d v1 = vertices[i];
 115                 for (int j = i + 1; j < vertices.length; j++) {
 116                     Point3d v2 = vertices[j];
 117                     for (int k = j + 1; k < vertices.length; k++) {
 118                         Point3d v3 = vertices[k];
 119                         Plane3d p = new Plane3d(v1, v2, v3);
 120                         if (!facePlanes.contains(p)) {
 121                             final Face face = buildFace(p);
 122                             if (face != null) {
 123                                 faces.add(face);
 124                                 facePlanes.add(p);
 125                             }
 126                         }
 127                     }
 128                 }
 129             }
 130
 131             double dist = Double.MAX_VALUE;
 132             final Point3d centerOfMass = getCenterOfMass(faces);
 133             for (Face f : faces) {
 134                 dist = Math.min(dist, Math.abs(f.p.getDist(centerOfMass)));
 135             }
 136             return dist;
 137         }
 138
 139         private Point3d getCenterOfMass(ArrayList<Face> faces) {
 140             double x = 0;
 141             double y = 0;
 142             double z = 0;
 143             double vol = 0;
 144             final Point3d p1 = vertices[0];
 145             for (Face f : faces) {
 146                 Point3d p2 = f.v[0];
 147                 for (int i = 1; i < f.v.length - 1; i++) {
 148                     Point3d p3 = f.v[i];
 149                     Point3d p4 = f.v[i + 1];
 150                     final double thisVol = getVolume(p1, p2, p3, p4);
 151                     final Point3d thisCentroid = getCentroid(p1, p2, p3, p4);
 152                     vol += thisVol;
 153                     x += thisVol * thisCentroid.x;
 154                     y += thisVol * thisCentroid.y;
 155                     z += thisVol * thisCentroid.z;
 156                 }
 157             }
 158             return new Point3d(x / vol, y / vol, z / vol);
 159         }
 160
 161         private Point3d getCentroid(Point3d p1, Point3d p2, Point3d p3, Point3d p4) {
 162             return new Point3d(
 163                     (p1.x + p2.x + p3.x + p4.x) / 4,
 164                     (p1.y + p2.y + p3.y + p4.y) / 4,
 165                     (p1.z + p2.z + p3.z + p4.z) / 4);
 166         }
 167
 168         private double getVolume(Point3d p1, Point3d p2, Point3d p3, Point3d p4) {
 169             final double dx1 = p2.x - p1.x;
 170             final double dy1 = p2.y - p1.y;
 171             final double dz1 = p2.z - p1.z;
 172             final double dx2 = p3.x - p1.x;
 173             final double dy2 = p3.y - p1.y;
 174             final double dz2 = p3.z - p1.z;
 175             final double dx3 = p4.x - p1.x;
 176             final double dy3 = p4.y - p1.y;
 177             final double dz3 = p4.z - p1.z;
 178             return Math.abs(
 179                 (dx1 * (dy2 * dz3 - dz2 * dy3) -
 180                 dy1 * (dx2 * dz3 - dz2 * dx3) +
 181                 dz1 * (dx2 * dy3 - dy2 * dx3))) / 6.0;
 182         }
 183
 184         private Face buildFace(Plane3d p) {
 185             final ArrayList<Point3d> verticesList = new ArrayList<Point3d>();
 186             boolean positive = false;
 187             boolean negative = false;
 188             for (int i = 0; i < vertices.length; i++) {
 189                 final Point3d v = vertices[i];
 190                 double dist = p.getDist(v);
 191                 if (Math.abs(dist) > EPSILON) {
 192                     if (dist > 0) {
 193                         positive = true;
 194                     } else {
 195                         negative = true;
 196                     }
 197                     if (positive && negative) {
 198                         return null;
 199                     }
 200                 } else {
 201                     verticesList.add(v);
 202                 }
 203             }
 204
 205             final Point3d[] vertices = new Point3d[verticesList.size()];
 206             verticesList.toArray(vertices);
 207             final AngleComparator angleComparator = new AngleComparator(p, vertices[0]);
 208             Arrays.sort(vertices, 1, vertices.length, angleComparator);
 209             return new Face(p, vertices);
 210         }
 211     }
 212
 213     static class AngleComparator implements Comparator<Point3d> {
 214         private final double nxx;
 215         private final double nxy;
 216         private final double nxz;
 217         private final double nyx;
 218         private final double nyy;
 219         private final double nyz;
 220         private final double x0;
 221         private final double y0;
 222
 223         AngleComparator(Plane3d p, Point3d origin) {
 224             if (Math.abs(p.a) > EPSILON || Math.abs(p.b) > EPSILON) {
 225                 nxx = -p.b;
 226                 nxy = p.a;
 227                 nxz = 0;
 228             } else {
 229                 nxx = 0;
 230                 nxy = -p.c;
 231                 nxz = p.b;
 232             }
 233
 234             nyx = nxy * p.c - nxz * p.b;
 235             nyy = nxz * p.a - nxx * p.c;
 236             nyz = nxx * p.b - nxy * p.a;
 237
 238             assert Math.abs(p.a * nxx + p.b * nxy + p.c * nxz) < EPSILON;
 239             assert Math.abs(p.a * nyx + p.b * nyy + p.c * nyz) < EPSILON;
 240
 241             x0 = origin.x * nxx + origin.y * nxy + origin.z * nxz;
 242             y0 = origin.x * nyx + origin.y * nyy + origin.z * nyz;
 243         }
 244
 245         public int compare(Point3d o1, Point3d o2) {
 246             final double x1 = o1.x * nxx + o1.y * nxy + o1.z * nxz - x0;
 247             final double y1 = o1.x * nyx + o1.y * nyy + o1.z * nyz - y0;
 248             final double x2 = o2.x * nxx + o2.y * nxy + o2.z * nxz - x0;
 249             final double y2 = o2.x * nyx + o2.y * nyy + o2.z * nyz - y0;
 250             final double prod = x1 * y2 - x2 * y1;
 251             if (prod < -EPSILON) {
 252                 return -1;
 253             } else if (prod > EPSILON) {
 254                 return +1;
 255             } else {
 256                 return 0;
 257             }
 258         }
 259     }
 260
 261     public static void main(String[] args) {
 262         new Thread(new asteroids_mb()).start();
 263     }
 264
 265     public void run() {
 266         try {
 267             final Scanner in = new Scanner(new FileReader("asteroids.in"));
 268             final PrintWriter out = new PrintWriter("asteroids.out");
 269
 270             Polyhedron p1 = Polyhedron.read(in);
 271             Polyhedron p2 = Polyhedron.read(in);
 272
 273             out.println(p1.getDist() + p2.getDist());
 274
 275             in.close();
 276             out.close();
 277         } catch (IOException e) {
 278             e.printStackTrace();
 279         }
 280     }
 281 }