NEERC/asteroids/asteroids_rs.java

   1 import java.io.*;
   2 import java.util.*;
   3
   4 public class asteroids_rs implements Runnable {
   5     private BufferedReader in;
   6     private PrintWriter out;
   7
   8     private void check(boolean expr, String msg) {
   9         if (!expr) {
  10             throw new Error(msg);
  11         }
  12     }
  13
  14     private void checkBounds(int n, int low, int hi, String nStr) {
  15         check((low <= n) && (n <= hi), nStr + " is not in [" + low + ", " + hi + "]");
  16     }
  17
  18     private class Polyhedron {
  19         private int[] x, y, z;
  20         private int n;
  21         private List<List<Integer>> facets;
  22         private long vpa, vpb, vpc, vpd;
  23         private double xc, yc, zc;
  24         private double minDist;
  25
  26         private void vectorProduct(int i, int j, int k) {
  27             int dx1 = x[j] - x[i];
  28             int dy1 = y[j] - y[i];
  29             int dz1 = z[j] - z[i];
  30             int dx2 = x[k] - x[i];
  31             int dy2 = y[k] - y[i];
  32             int dz2 = z[k] - z[i];
  33             vpa = dy1 * dz2 - dy2 * dz1;
  34             vpb = -(dx1 * dz2 - dx2 * dz1);
  35             vpc = dx1 * dy2 - dx2 * dy1;
  36             vpd = -vpa * x[i] - vpb * y[i] - vpc * z[i];
  37         }
  38
  39         private void checkConvexFacet(long a, long b, long c, long d, List<Integer> facet) {
  40             int m = facet.size();
  41             int num1 = facet.get(0);
  42             for (int i = 1; i < m; i++) {
  43                 for (int j = 1; j + 1 < m; j++) {
  44                     int num2 = facet.get(j);
  45                     int num3 = facet.get(j + 1);
  46                     vectorProduct(num1, num2, num3);
  47                     long sp = a * vpa + b * vpb + c * vpc;
  48                     check(sp != 0, "Three points on a line");
  49                     if (sp < 0) {
  50                         facet.set(j, num3);
  51                         facet.set(j + 1, num2);
  52                     }
  53                 }
  54             }
  55             for (int i = 0; i < m; i++) {
  56                 for (int j = i + 1; j < m; j++) {
  57                     for (int k = j + 1; k < m; k++) {
  58                         vectorProduct(facet.get(i), facet.get(j), facet.get(k));
  59                         long sp = a * vpa + b * vpb + c * vpc;
  60                         check(sp > 0, "Facet not convex");
  61                     }
  62                 }
  63             }
  64         }
  65
  66         public Polyhedron() throws IOException {
  67             n = Integer.parseInt(in.readLine());
  68             checkBounds(n, 1, 100, "n");
  69             x = new int[n];
  70             y = new int[n];
  71             z = new int[n];
  72             for (int i = 0; i < n; i++) {
  73                 StringTokenizer st = new StringTokenizer(in.readLine());
  74                 x[i] = Integer.parseInt(st.nextToken());
  75                 y[i] = Integer.parseInt(st.nextToken());
  76                 z[i] = Integer.parseInt(st.nextToken());
  77             }
  78
  79             facets = new ArrayList<List<Integer>>();
  80             for (int i = 0; i < n; i++) {
  81                 for (int j = i + 1; j < n; j++) {
  82                     LOOPK:
  83                     for (int k = j + 1; k < n; k++) {
  84                         vectorProduct(i, j, k);
  85                         long a = vpa;
  86                         long b = vpb;
  87                         long c = vpc;
  88                         long d = vpd;
  89
  90                         boolean negative = false;
  91                         boolean positive = false;
  92                         for (int u = 0; u < n; u++) {
  93                             long dist = a * x[u] + b * y[u] + c * z[u] + d;
  94                             if (dist < 0) {
  95                                 negative = true;
  96                             } else if (dist > 0) {
  97                                 positive = true;
  98                             } else {
  99                                 if ((u < k) && (u != i) && (u != j)) {
 100                                     continue LOOPK;
 101                                 }
 102                             }
 103                         }
 104                         if (positive && negative) {
 105                             continue;
 106                         }
 107
 108                         List<Integer> facet = new ArrayList<Integer>();
 109                         facet.add(i);
 110                         facet.add(j);
 111                         facet.add(k);
 112                         for (int u = k + 1; u < n; u++) {
 113                             if (a * x[u] + b * y[u] + c * z[u] + d == 0) {
 114                                 facet.add(u);
 115                             }
 116                         }
 117 //                        System.err.println(Arrays.toString(facet.toArray()));
 118                         checkConvexFacet(a, b, c, d, facet);
 119                         facets.add(facet);
 120                     }
 121                 }
 122             }
 123             check(facets.size() > 1, "polyhedron is degenerate");
 124
 125             long totalVolume = 0;
 126             long x0 = 0;
 127             long y0 = 0;
 128             long z0 = 0;
 129             for (List<Integer> facet: facets) {
 130                 int m = facet.size();
 131                 int num1 = facet.get(0);
 132                 for (int i = 0; i < m; i++) {
 133                     int num2 = facet.get(i);
 134                     int num3 = facet.get((i + 1) % m);
 135                     long volume = calcVolume(0, num1, num2, num3);
 136                     totalVolume += volume;
 137                     x0 += Math.abs(volume) * (x[num1] + x[num2] + x[num3] + x[0]);
 138                     y0 += Math.abs(volume) * (y[num1] + y[num2] + y[num3] + y[0]);
 139                     z0 += Math.abs(volume) * (z[num1] + z[num2] + z[num3] + z[0]);
 140                 }
 141             }
 142             xc = 1.0 * x0 / totalVolume / 4.0;
 143             yc = 1.0 * y0 / totalVolume / 4.0;
 144             zc = 1.0 * z0 / totalVolume / 4.0;
 145 //            System.err.println(xc + " " + yc + " " + zc);
 146 //            System.err.println(totalVolume);
 147
 148             minDist = Double.MAX_VALUE;
 149             for (List<Integer> facet: facets) {
 150                 vectorProduct(facet.get(0), facet.get(1), facet.get(2));
 151                 double norm = Math.sqrt(vpa * vpa + vpb * vpb + vpc * vpc);
 152                 double dist = (vpa * xc + vpb * yc + vpc * zc + vpd) / norm;
 153                 minDist = Math.min(minDist, Math.abs(dist));
 154             }
 155         }
 156
 157         private long calcVolume(int a, int b, int c, int d) {
 158             vectorProduct(a, c, d);
 159             return Math.abs((x[b] - x[a]) * vpa + (y[b] - y[a]) * vpb + (z[b] - z[a]) * vpc);
 160         }
 161     }
 162
 163     private void solve() throws IOException {
 164         Polyhedron p1 = new Polyhedron();
 165         Polyhedron p2 = new Polyhedron();
 166         out.printf("%.6f\n", p1.minDist + p2.minDist);
 167     }
 168
 169     public static void main(String[] args) {
 170         new Thread(new asteroids_rs()).start();
 171     }
 172
 173     public void run() {
 174         String problem = getClass().getName().split("_")[0];
 175         try {
 176             Locale.setDefault(Locale.US);
 177             in = new BufferedReader(new FileReader(new File(problem + ".in")));
 178             out = new PrintWriter(new File(problem + ".out"));
 179             solve();
 180             in.close();
 181             out.close();
 182         } catch (IOException e) {
 183             e.printStackTrace();
 184             System.exit(1);
 185         }
 186     }
 187 }