1 /* Lines and Circles, MCPC 2008 Solution by Andy Harrington
  2  *
  3  * pi + t*vi = pj + s*vj
  4  * (pi + t*vi)Xvj = (pj + s*vj)Xvj  X means z comp of X prod
  5  * piXvj + t*(viXvj) = pjXvj
  6  * t = (pj - pi)Xvj/viXvj
  7  * intersection pt = pi + t*vi
  8 */
  9 
 10 import java.util.*;
 11 import java.io.*;
 12 import static java.lang.Math.*;
 13 
 14 public class lc
 15 {
 16     static Scanner in;
 17     static final int MAX_SHAPES = 25;
 18     static final int MAX_PT = MAX_SHAPES * (MAX_SHAPES + 2);
 19     static int dataset = 1;
 20     static double[][] D;// = new double[MAX_PT][MAX_PT];
 21     static int[] R = new int[MAX_SHAPES];
 22     static double[][] end0 = new double[MAX_SHAPES][]; //line init endpt
 23     static double[][] center = end0;                   // or center
 24     static double[][] end1 = new double[MAX_SHAPES][]; // line endpt2
 25     static double[][] segV = new double[MAX_SHAPES][];// (endpt1 - endpt0)
 26     static double[][] uVec = new double[MAX_SHAPES][];// (endpt1 - endpt0)/length
 27     static boolean[] isLn = new boolean[MAX_SHAPES];
 28     static double[][] pt = new double[MAX_PT][];
 29     static ArrayList<ArrayList<Integer>> intercept =
 30                                                new ArrayList<ArrayList<Integer>>();
 31     static int pts, shapes;
 32 
 33     public static void main(String[] args) throws Exception {
 34         String file = (args.length > 0) ? args[0] : "maze.in";
 35         in = new Scanner(new File(file));
 36         char type = in.next().charAt(0);
 37         while (type  != '*') {
 38             intercept.clear();
 39             shapes = 0;
 40             while (type == 'L' || type == 'C') {
 41                 intercept.add(new ArrayList<Integer>());
 42                 isLn[shapes] = type == 'L';
 43                 end0[shapes] = new double[]{in.nextInt(), in.nextInt()};
 44                 if (isLn[shapes]) {
 45                     end1[shapes] = new double[]{in.nextInt(), in.nextInt()};
 46                     segV[shapes] = dif(end1[shapes], end0[shapes]);
 47                     uVec[shapes] = unit(segV[shapes]);
 48                 }
 49                 else
 50                     R[shapes] = in.nextInt();
 51                 shapes++;
 52                 type = in.next().charAt(0);
 53             }
 54             solve();
 55             dataset++;
 56             type = in.next().charAt(0);
 57         }
 58     }
 59 
 60     // dot product
 61     static double dot(double[] v1, double[] v2) {
 62         return v1[0]*v2[0] + v1[1]*v2[1];
 63     }
 64 
 65     static double angle(double[] v) {
 66         return atan2(v[1], v[0]);
 67     }
 68 
 69     // z coord of cross product
 70     static double cross(double[] v1, double[] v2) {
 71         return v1[1]*v2[0] - v1[0]*v2[1];
 72     }
 73 
 74     // vector difference of two points
 75     static double[] dif(double[] p1, double[] p2) {
 76         return new double[] {p1[0] - p2[0], p1[1] - p2[1]};
 77     }
 78 
 79     // return p +tv
 80     static double[] shift(double[] p, double t, double[] v) {
 81         return new double[] {p[0] + t * v[0], p[1] + t * v[1]};
 82     }
 83 
 84     // normal vector (for when want both so sign does not matter)
 85     static double[] normal(double[] v) {
 86         return new double[] {-v[1], v[0]};
 87     }
 88 
 89     static double length(double[] v) {
 90         return sqrt(dot(v, v));
 91     }
 92 
 93     static double[] unit(double[] v) {
 94         double m = length(v);
 95         return new double[] {v[0]/m, v[1]/m};
 96     }
 97 
 98     static void addIntercept(double[] p, int i, int j) {
 99         if ((!isLn[i] || onSeg(i, p)) && (!isLn[j] || onSeg(j, p)) ) {
100             intercept.get(i).add(pts);
101             if (i!=j)
102                 intercept.get(j).add(pts);
103             pt[pts] = p;
104             pts++;
105         }
106     }
107 
108     // assume p is on line i - now check if in segment
109     static boolean onSeg(int i, double[] p) {
110         return dot(segV[i], dif(p, end0[i])) >= 0 &&  // right ray1
111                dot(segV[i], dif(p, end1[i])) <= 0;  // right ray2
112     }
113 
114     static void solve() {
115         final double BIG = 1000000;
116         for (int i = 0; i < shapes; i++) {
117           if (isLn[i]) {
118               addIntercept(end0[i], i, i);
119               addIntercept(end1[i], i, i);
120           }
121           for (int j = i+1; j < shapes; j++) {
122               if (isLn[i] && isLn[j]) {  /// line intersection
123                   double denom = cross(segV[i], segV[j]);
124                   if (denom != 0) {  // not parallel
125                       double t = cross(dif(end0[j], end0[i]), segV[j])/denom;
126                       addIntercept(shift(end0[i], t, segV[i]), i, j);
127                   }
128               }
129               else if (!isLn[i] && !isLn[j]) {  // circles
130                   double[] dc = dif(center[j], center[i]);
131                   double sep = length(dc),
132                          s = .5*(sep*sep + R[i]*R[i] - R[j]*R[j])/sep,
133                          t2 = R[i]*R[i] - s*s;
134                   if (t2 >= 0) {
135                       double[] dcUnit = unit(dc),
136                                n = normal(dcUnit),
137                                mid = shift(center[i], s, dcUnit);
138                       addIntercept(shift(mid, sqrt(t2), n), i, j);
139                       addIntercept(shift(mid, -sqrt(t2), n), i, j);
140                   }
141              }
142              else { // one of each
143                  int ic = i, il = j;
144                  if (isLn[i]) {
145                      ic = j;
146                      il = i;
147                  }
148                  double t = dot(dif(center[ic], end0[il]), uVec[il]);
149                  double[] close = shift(end0[il], t, uVec[il]);
150                  double s = length(dif(center[ic], close)),
151                          t2 = R[ic]*R[ic] - s*s;
152                  if (t2 >= 0) {
153                      addIntercept(shift(close, sqrt(t2), uVec[il]), i, j);
154                      addIntercept(shift(close, -sqrt(t2), uVec[il]), i, j);
155                  }
156             }
157           }
158         }
159         D = new double[pts][pts];
160         for (int i = 0; i < pts; i++)
161             for (int j = 0; j < pts; j++)
162                 D[i][j] = BIG;
163         // find distances between points on same object
164         for (int i = 0; i < shapes; i++)
165             for (int j : intercept.get(i))
166                 for (int k : intercept.get(i))
167                     if (isLn[i])
168                         D[j][k] = length(dif(pt[j], pt[k]));
169                     else {
170                         double a = abs(angle(dif(pt[j], center[i])) -
171                                        angle(dif(pt[k], center[i])));
172                         if (a > PI)
173                             a = 2*PI - a;
174                         D[j][k] = min(D[j][k], R[i]*a);
175                     }
176         for (int k = 0; k < pts; k++)
177             for (int i = 0; i < pts; i++)
178                 for (int j = 0; j < pts; j++)
179                     D[i][j] = min(D[i][j], D[i][k] + D[k][j]);
180         double longest = 0;
181         for (int i = 0; i < pts; i++)
182             for (int j = 0; j < pts; j++)
183                 if (D[i][j] < BIG && D[i][j] > longest)
184                     longest = D[i][j];
185         System.out.format("Case %d: %.1f%n", dataset, longest);
186     }
187 }