1 /* maze.java Solution by Ron Pacheco <ron@pacheco.net> 
  2    2008 ACM Mid-Central Regional Contest
  3    Problem G: Line & Circle Maze */
  4 
  5 import java.io.*;
  6 import java.util.*;
  7 
  8 /* The endpoints of all line segments along with all object intersections form
  9    a weighted graph on which we use an all-pairs shortest path algorithm. A
 10    conceptually easy solution but challenging to implement! 
 11    
 12    Here is a sketch of this program's approach:
 13    
 14    1) Construct a set of points containing all line endpoints and all object
 15       intersections.
 16       
 17    2) Compute the distances (either linear distance or circular arc length)
 18       between all pairs of points that lie on the same object. To facilitate
 19       this, Step 1 keeps a list of all the objects incident to each point.
 20       
 21    3) Construct an adjacency matrix from the distances found in Step 2.
 22    
 23    4) Use the simple Floyd-Warshall all-pairs shortest path algorithm.
 24    
 25    5) Search all pairs for the longest minimum path.
 26  */
 27 
 28 class maze {
 29 
 30   // The critical data structure! The points object is a mapping of points to
 31   // the set of objects incident to that point.
 32   static TreeMap<Point,HashSet<Object>> points;
 33 
 34   public static void main( String[] args ) throws Exception {
 35 
 36     // Open file specified on command line, else "maze.in"
 37     Scanner in = new Scanner( new File( args.length > 0 ? args[0] : "maze.in" ) );
 38 
 39     // Track the input case number
 40     int caseNumber = 0;
 41 
 42     // First character of input case; "*" means end of input
 43     char ch = in.next().charAt(0);
 44     while ( ch != '*' ) {
 45 
 46       // The shapes object holds all the input shapes. When I first coded this
 47       // solution there wasn't a cap on the number of objects. Later we
 48       // introduced a maximum of 25 objects, so this could just as easily now
 49       // be a simple array.
 50       ArrayList<Object> shapes = new ArrayList<Object>();
 51 
 52       // Loop through all the input lines and add the shapes
 53       while ( ch == 'L' || ch == 'C' ) {
 54         shapes.add( ch == 'L'
 55           ? new Line( in.nextInt(), in.nextInt(), in.nextInt(), in.nextInt() )
 56           : new Circle( in.nextInt(), in.nextInt(), in.nextInt() ) );
 57         in.nextLine();
 58         ch = in.next().charAt(0);
 59       }
 60 
 61       // Init points structure for the new test case
 62       points = new TreeMap<Point,HashSet<Object>>( new PointComparator() );
 63 
 64       // Look for intersections between every possible pair of objects
 65       for ( int i = 0; i < shapes.size(); i++ ) {
 66         Object s = shapes.get(i);
 67 
 68         // For line objects, add their endpoints to the points map
 69         if ( s instanceof Line ) {
 70           addPoint( new Point( ((Line)s).x1, ((Line)s).y1 ), s );
 71           addPoint( new Point( ((Line)s).x2, ((Line)s).y2 ), s );
 72         }
 73 
 74         // Inner loop comparing all pairs of shapes
 75         for ( int j = i + 1; j < shapes.size(); j++ ) {
 76           Object t = shapes.get(j);
 77 
 78           // Two line segments
 79           if ( s instanceof Line && t instanceof Line ) {
 80             Point p = MyMath.xLineLine( (Line)s, (Line)t );
 81             if ( p != null ) {
 82               addPoint( p, s );
 83               addPoint( p, t );
 84             }
 85           }
 86 
 87           // Two circles
 88           else if ( s instanceof Circle && t instanceof Circle ) {
 89             ArrayList<Point> intersections = MyMath.xCircleCircle( (Circle)s, (Circle)t );
 90             if ( intersections != null ) {
 91               Iterator k = intersections.iterator();
 92               while ( k.hasNext() ) {
 93                 Point p = (Point)k.next();
 94                 addPoint( p, s );
 95                 addPoint( p, t );
 96               }
 97             }
 98           }
 99 
100           // A line and a circle
101           else {
102             ArrayList<Point> intersections;
103             if ( s instanceof Line )
104               intersections = MyMath.xLineCircle( (Line)s, (Circle)t );
105             else
106               intersections = MyMath.xLineCircle( (Line)t, (Circle)s );
107             if ( intersections != null ) {
108               Iterator k = intersections.iterator();
109               while ( k.hasNext() ) {
110                 Point p = (Point)k.next();
111                 addPoint( p, s );
112                 addPoint( p, t );
113               }
114             }
115           }
116         }
117       }
118 
119       // Initialize the graph to infinitely weighted edges
120       int N = points.size();
121       double graph[][] = new double[N][N];
122       for ( int i = 0; i < N; i++ )
123         for ( int j = 0; j < N; j++ )
124           if ( i == j )
125             graph[i][j] = 0;
126           else
127             graph[i][j] = MyMath.INFINITY;
128 
129       // For every point...
130       for ( Iterator i1 = points.keySet().iterator(); i1.hasNext(); ) {
131         Point p = (Point)i1.next();
132 
133         // and every object the point intersects...
134         for ( Iterator i2 = points.get(p).iterator(); i2.hasNext(); ) {
135           Object s = i2.next();
136 
137           // and every other point on the same object . . .
138           for ( Iterator i3 = points.keySet().iterator(); i3.hasNext(); ) {
139             Point q = (Point)i3.next();
140             if ( p.n != q.n && points.get(q).contains( s ) ) {
141               // find the distance between the points.
142               if ( s instanceof Line )
143                 graph[p.n][q.n] = graph[q.n][p.n] = MyMath.linearDistance( p, q );
144               else
145                 graph[p.n][q.n] = graph[q.n][p.n] = MyMath.arcLength( (Circle)s, p, q );
146             }
147           }
148         }
149       }
150 
151       // Finally, the easiest part of the whole thing! Run the Floyd-Warshall
152       // all pairs shortest path algorithm.
153       for ( int k = 0; k < N; k++ )
154         for ( int i = 0; i < N; i++ )
155           for ( int j = 0; j < N; j++ )
156             graph[i][j] = Math.min( graph[i][j], graph[i][k] + graph[k][j] );
157 
158       // If no lines and no intersection just say "No Solution". (Note that this
159       // situation is prevented from occuring in the offical problem statement.)
160       if ( N == 0 ) {
161         System.out.format( "Case %d: No Solution%n", ++caseNumber );
162       }
163 
164       // Otherwise find the longest of the shortest paths and output its length
165       else {
166         double m = 0;
167         for ( int i = 0; i < N; i++ )
168           for ( int j = 0; j < N; j++ )
169             if ( !MyMath.isInfinite( graph[i][j] ) )
170               m = Math.max( m, graph[i][j] );
171         System.out.format( "Case %d: %.1f%n", ++caseNumber, m );
172       }
173 
174       // Try for another test case
175       in.nextLine();
176       ch = in.next().charAt(0);
177     }
178   }
179 
180   // Utility function to add to the points data structure. If the point is
181   // is already in the map, just add the object to the set of objects this
182   // point intersects, otherwise add a new mapping with this point and object.
183 
184   static void addPoint( Point p, Object s ) {
185     HashSet<Object> on;
186     if ( points.containsKey( p ) )
187       on = points.get( p );
188     else {
189       p = new Point( points.size(), p );
190       on = new HashSet<Object>();
191     }
192     on.add( s );
193     points.put( p, on );
194   }
195 
196 }
197 
198 // Classes for Line and Circle so that they can be stored in the same
199 // collections.
200 
201 class Line {
202   public int x1, y1, x2, y2;
203   public Line( int x1, int y1, int x2, int y2 ) { this.x1 = x1; this.y1 = y1; this.x2 = x2; this.y2 = y2; }
204 }
205 
206 class Circle {
207   public int x, y, r;
208   public Circle( int x, int y, int r ) { this.x = x; this.y = y; this.r = r; }
209 }
210 
211 // Point class. In addition to (x,y), we store n, which is just a unique index
212 // number assigned to the point so that later we can easily create an adjacency
213 // matrix from the points map.
214 
215 class Point {
216   int n;
217   public double x, y;
218   public Point( double x, double y ) { this.x = x; this.y = y; }
219   public Point( int n, Point p ) { this.n = n; this.x = p.x; this.y = p.y; }
220 }
221 
222 // Since we're dealing with floating point approximations to real numbers, use
223 // a comparator for points that takes our float epsilon into account.
224 
225 class PointComparator implements Comparator<Point> {
226   public int compare( Point a, Point b ) {
227     if ( MyMath.ltDouble( a.x, b.x ) )
228       return -1;
229     else if ( MyMath.gtDouble( a.x, b.x ) )
230       return 1;
231     else {
232       if ( MyMath.ltDouble( a.y, b.y ) )
233         return -1;
234       else if ( MyMath.gtDouble( a.y, b.y ) )
235         return 1;
236       else
237         return 0;
238     }
239   }
240 }
241 
242 // There was enough math in this problem that I decided to pull it all out into
243 // a separate class because it was cluttering up the main algorithm.
244 
245 class MyMath {
246 
247   // Epsilon and infinity constants sufficient for this problem
248 
249   public static final double EPSILON = 1E-8;
250   public static final double INFINITY = 1E+8;
251 
252   // Floating point epsilon-based comparisons
253 
254   public static boolean eqDouble( double a, double b ) { return a >= b - EPSILON && a <= b - EPSILON; }
255 
256   public static boolean ltDouble( double a, double b ) { return b - a > EPSILON; }
257 
258   public static boolean gtDouble( double a, double b ) { return a - b > EPSILON; }
259 
260   public static boolean isInfinite( double a ) { return !ltDouble( a, INFINITY ); }
261 
262   // The math algorithms. Many other implementations are possible. See any
263   // decent reference on geometric algorithms.
264 
265   public static Point xLineLine( Line l1, Line l2 ) {
266     int x1 = l1.x1, y1 = l1.y1, x2 = l1.x2, y2 = l1.y2, x3 = l2.x1, y3 = l2.y1, x4 = l2.x2, y4 = l2.y2;
267     int d = ( y4 - y3 ) * ( x2 - x1 ) - ( x4 - x3 ) * ( y2 - y1 );
268     if ( d == 0 ) return null;
269     double a = ( ( x4 - x3 ) * ( y1 - y3 ) - ( y4 - y3 ) * ( x1 - x3 ) ) / (double)d;
270     double b = ( ( x2 - x1 ) * ( y1 - y3 ) - ( y2 - y1 ) * ( x1 - x3 ) ) / (double)d;
271     if ( a < 0 || a > 1 || b < 0 || b > 1 ) return null;
272     return new Point( x1 + a * ( x2 - x1 ), y1 + a * ( y2 - y1 ) );
273   }
274 
275   public static ArrayList<Point> xLineCircle( Line l, Circle c ) {
276     int dx = l.x2 - l.x1;
277     int dy = l.y2 - l.y1;
278     int A = dx * dx + dy * dy;
279     int B = 2 * ( dx * ( l.x1 - c.x ) + dy * ( l.y1 - c.y ) );
280     int C = ( l.x1 - c.x ) * ( l.x1 - c.x ) + ( l.y1 - c.y ) * ( l.y1 - c.y ) - c.r * c.r;
281     int D = B * B - 4 * A * C;
282     if ( D <= 0 ) return null;
283     ArrayList<Point> points = new ArrayList<Point>( 2 );
284     double t = ( -B + Math.sqrt( D ) ) / ( 2 * A );
285     if ( t >= 0 && t <= 1 ) points.add( new Point( l.x1 + t * dx, l.y1 + t * dy ) );
286     t = ( -B - Math.sqrt( D ) ) / ( 2 * A );
287     if ( t >= 0 && t <= 1 ) points.add( new Point( l.x1 + t * dx, l.y1 + t * dy ) );
288     return points;
289   }
290 
291   public static ArrayList<Point> xCircleCircle( Circle c1, Circle c2 ) {
292     int dx = c2.x - c1.x;
293     int dy = c2.y - c1.y;
294     double d = Math.sqrt( dx * dx + dy * dy );
295     if ( d > c1.r + c2.r || d < Math.abs( c1.r - c2.r ) ) return null;
296     double a = ( c1.r * c1.r  - c2.r * c2.r  + d * d ) / ( 2 * d );
297     double x = c1.x + dx * a / d;
298     double y = c1.y + dy * a / d;
299     double h = Math.sqrt( c1.r * c1.r - a * a );
300     double rx = -dy * h / d;
301     double ry = dx * h / d;
302     ArrayList<Point> points = new ArrayList<Point>( 2 );
303     points.add( new Point( x + rx, y + ry ) );
304     points.add( new Point( x - rx, y - ry ) );
305     return points;
306   }
307 
308   public static double linearDistance( Point p, Point q ) {
309     return Math.sqrt( ( p.x - q.x ) * ( p.x - q.x ) + ( p.y - q.y ) * ( p.y - q.y ) );
310   }
311 
312   public static double arcLength( Circle c, Point p, Point q ) {
313     double theta = Math.abs( Math.atan2( p.y - c.y, p.x - c.x ) - Math.atan2( q.y - c.y, q.x - c.x ) );
314     return c.r * Math.min( theta, 2 * Math.PI - theta );
315   }
316 
317 }