NEERC/asteroids/asteroids_gk.java

   1 import java.util.*;
   2 import java.io.*;
   3
   4 class asteroids_gk {
   5         static Scanner in;
   6         static PrintWriter out;
   7         static final double EPS = 1e-10;
   8         static Point magic = new Point(Math.E, Math.PI, Math.E * Math.PI);
   9
  10         static class Point {
  11                 double x, y, z;
  12                 Point(double x, double y, double z) { this.x = x; this.y = y; this.z = z; }
  13                 Point plus(Point p) { return new Point(x + p.x, y + p.y, z + p.z); }
  14                 Point minus(Point p) { return new Point(x - p.x, y - p.y, z - p.z); }
  15                 double dot(Point p) { return x * p.x + y * p.y + z * p.z; }
  16                 Point cross(Point p) { return new Point(y * p.z - z * p.y, z * p.x - x * p.z, x * p.y - y * p.x );}
  17                 double norm() { return Math.sqrt(dot(this)); }
  18                 Point scale(double a) { return new Point(x * a, y * a, z * a); }
  19                 double normM() { return dot(this) * Math.signum(dot(magic)); }
  20
  21                 double angle(final Point c, final Point base) {
  22                         Point p = minus(c);
  23                         return Math.atan2(p.cross(base).normM(), p.dot(base));
  24                 }
  25         }
  26
  27         static class Averager {
  28                 Point p = new Point(0, 0, 0);
  29                 double w = 0;
  30
  31                 void add(Point dp, double dw) {
  32                         p = p.plus(dp.scale(dw));
  33                         w += dw;
  34                 }
  35
  36                 Point get(double a) {
  37                         return p.scale(a / w);
  38                 }
  39         }
  40
  41         List<Point> on(Point[] points, int i, int j, int k) {
  42                 Point normal = normal(points[j], points[i], points[k]);
  43                 double d = normal.dot(points[i]);
  44                 boolean neg = false;
  45                 boolean pos = false;
  46                 List<Point> on = new ArrayList<Point>();
  47                 for (int q = 0; q < points.length; q++) {
  48                         double dist = normal.dot(points[q]) - d;
  49                         if (Math.abs(dist) < EPS) {
  50                                 on.add(points[q]);
  51                         } else if ((neg |= dist < 0) & (pos |= dist > 0)) {
  52                                 return null;
  53                         }
  54                 }
  55                 return on;
  56         }
  57
  58         Point normal(Point p1, Point p2, Point p3) {
  59                 return p1.minus(p2).cross(p3.minus(p2));
  60         }
  61
  62         double calcDist() {
  63                 int n = in.nextInt();
  64
  65                 Point[] points = new Point[n];
  66                 for (int i = 0; i < n; i++) {
  67                         points[i] = new Point(in.nextInt(), in.nextInt(), in.nextInt());
  68                 }
  69
  70                 List<List<Point>> faces = new ArrayList<List<Point>>();
  71                 for (int i = 0; i < n; i++) {
  72                         for (int j = i + 1; j < n; j++) {
  73                                 for (int k = j + 1; k < n; k++) {
  74                                         List<Point> on = on(points, i, j, k);
  75                                         if (on != null && on.get(2) == points[k]) {
  76                                                 faces.add(on);
  77                                         }
  78                                 }
  79                         }
  80                 }
  81
  82                 Point first = points[0];
  83                 Averager mma = new Averager();
  84                 for (List<Point> face : faces) {
  85                         Averager ca = new Averager();
  86                         for (Point p : face) {
  87                                 ca.add(p, 1);
  88                         }
  89                         final Point c = ca.get(1);
  90                         final Point base = face.get(0).minus(c);
  91                         Collections.sort(face, new Comparator<Point>() {
  92                                 @Override
  93                                 public int compare(Point p1, Point p2) {
  94                                         return Double.compare(p1.angle(c, base), p2.angle(c, base));
  95                                 }
  96                         });
  97
  98
  99                         int f = face.size();
 100                         Averager ma = new Averager();
 101                         for (int q = 0; q < f; q++) {
 102                                 Point p1 = face.get(q).minus(c);
 103                                 Point p2 = face.get((q + f - 1) % f).minus(c);
 104                                 ma.add(p1.plus(p2), p1.cross(p2).norm());
 105                         }
 106
 107                         Point mc = ma.get(1.0 / 3).plus(c).minus(first);
 108                         Point normal = normal(face.get(0), face.get(1), face.get(2));
 109                         mma.add(mc, Math.abs(ma.w * normal.dot(mc)) / normal.norm());
 110                 }
 111                 Point mmc = mma.get(3.0 / 4).plus(first);
 112
 113                 double min = Double.MAX_VALUE;
 114                 for (List<Point> face : faces) {
 115                         Point normal = normal(face.get(0), face.get(1), face.get(2));
 116                         min = Math.min(min, Math.abs(normal.dot(mmc) - normal.dot(face.get(0))) / normal.norm());
 117                 }
 118                 return min;
 119         }
 120
 121         void run() throws IOException {
 122                 out.println(calcDist() + calcDist());
 123         }
 124
 125         public static void main(String[] args) throws Exception {
 126                 in = new Scanner(new File("asteroids.in"));
 127                 out = new PrintWriter("asteroids.out");
 128
 129                 new asteroids_gk().run();
 130
 131                 in.close();
 132                 out.close();
 133         }
 134 }