1
2
3
4
5
6
7
8 import javax.swing.*;
9 import java.awt.*;
10 import java.awt.event.*;
11 import java.awt.geom.*;
12 import java.util.*;
13 import java.io.*;
14
15 class guimaze {
16
17 private static JFrame guiFrame;
18 private static MazeVisualizer maze;
19 private static JLabel statusLabel;
20 private static Scanner in;
21
22 static char ch;
23 static TreeMap<Point,HashSet<Object>> points;
24 static int caseNumber = 0;
25 static ArrayList<Object> shapes;
26 static int N;
27 static double graph[][];
28
29 public static void main( String[] args ) throws Exception {
30 in = new Scanner( new File( args.length > 0 ? args[0] : "maze.in" ) );
31 ch = in.next().charAt(0);
32 javax.swing.SwingUtilities.invokeLater( new Runnable() { public void run() { gui(); } } );
33 }
34
35 private static void gui() {
36 guiFrame = new JFrame( "Line & Circle Maze" );
37 guiFrame.setDefaultCloseOperation( JFrame.EXIT_ON_CLOSE );
38 guiFrame.getContentPane().setLayout( new BorderLayout() );
39 JPanel buttonPanel = new JPanel();
40 buttonPanel.setLayout( new FlowLayout() );
41 maze = new MazeVisualizer( 720, 720, -10, -10, 110, 110 );
42
43 JPanel statusPanel = new JPanel();
44 statusLabel = (JLabel)statusPanel.add( new JLabel( "Ready" ) );
45 ((JButton)buttonPanel.add( new JButton( "Next Data Set" ) )).addActionListener( new ButtonListener() );
46 guiFrame.getContentPane().add( BorderLayout.NORTH, buttonPanel );
47 guiFrame.getContentPane().add( BorderLayout.CENTER, maze );
48 guiFrame.getContentPane().add( BorderLayout.SOUTH, statusPanel );
49 guiFrame.pack();
50 guiFrame.setVisible( true );
51 }
52
53 private static class ButtonListener implements ActionListener {
54
55 public void actionPerformed( ActionEvent actionEvent ) {
56
57 String buttonName = ((JButton)actionEvent.getSource()).getText();
58 if ( buttonName.equals( "Next Data Set" ) ) {
59 if ( ch == '*' ) { guiFrame.dispose(); return; }
60 shapes = new ArrayList<Object>();
61 while ( ch == 'L' || ch == 'C' ) {
62 shapes.add( ch == 'L'
63 ? new Line( in.nextInt(), in.nextInt(), in.nextInt(), in.nextInt() )
64 : new Circle( in.nextInt(), in.nextInt(), in.nextInt() ) );
65 in.nextLine();
66 ch = in.next().charAt(0);
67 }
68 in.nextLine();
69 ch = in.next().charAt(0);
70 maze.clearShapes();
71 for ( int i = 0; i < shapes.size(); i++ ) {
72 Object s = shapes.get(i);
73 if ( s instanceof Line )
74 maze.addLine( ((Line)s).x1, ((Line)s).y1, ((Line)s).x2, ((Line)s).y2 );
75 else
76 maze.addCircle( ((Circle)s).x, ((Circle)s).y, ((Circle)s).r );
77 }
78
79 points = new TreeMap<Point,HashSet<Object>>( new PointComparator() );
80 for ( int i = 0; i < shapes.size(); i++ ) {
81 Object s = shapes.get(i);
82 if ( s instanceof Line ) {
83 addPoint( new Point( ((Line)s).x1, ((Line)s).y1 ), s );
84 addPoint( new Point( ((Line)s).x2, ((Line)s).y2 ), s );
85 }
86 for ( int j = i + 1; j < shapes.size(); j++ ) {
87 Object t = shapes.get(j);
88 if ( s instanceof Line && t instanceof Line ) {
89 Point p = MyMath.xLineLine( (Line)s, (Line)t );
90 if ( p != null ) {
91 addPoint( p, s );
92 addPoint( p, t );
93 }
94 }
95 else if ( s instanceof Circle && t instanceof Circle ) {
96 ArrayList<Point> intersections = MyMath.xCircleCircle( (Circle)s, (Circle)t );
97 if ( intersections != null ) {
98 Iterator k = intersections.iterator();
99 while ( k.hasNext() ) {
100 Point p = (Point)k.next();
101 addPoint( p, s );
102 addPoint( p, t );
103 }
104 }
105 }
106 else {
107 ArrayList<Point> intersections;
108 if ( s instanceof Line )
109 intersections = MyMath.xLineCircle( (Line)s, (Circle)t );
110 else
111 intersections = MyMath.xLineCircle( (Line)t, (Circle)s );
112 if ( intersections != null ) {
113 Iterator k = intersections.iterator();
114 while ( k.hasNext() ) {
115 Point p = (Point)k.next();
116 addPoint( p, s );
117 addPoint( p, t );
118 }
119 }
120 }
121 }
122 }
123 for ( Iterator i = points.keySet().iterator(); i.hasNext(); ) {
124 Point p = (Point)i.next();
125 maze.addPoint( p.x, p.y );
126 }
127 N = points.size();
128 graph = new double[N][N];
129 for ( int i = 0; i < N; i++ )
130 for ( int j = 0; j < N; j++ )
131 if ( i == j )
132 graph[i][j] = 0;
133 else
134 graph[i][j] = MyMath.INFINITY;
135 Point pointsById[] = new Point[ N ];
136 for ( Iterator i1 = points.keySet().iterator(); i1.hasNext(); ) {
137 Point p = (Point)i1.next();
138 pointsById[ p.n ] = p;
139 for ( Iterator i2 = points.get(p).iterator(); i2.hasNext(); ) {
140 Object s = i2.next();
141 for ( Iterator i3 = points.keySet().iterator(); i3.hasNext(); ) {
142 Point q = (Point)i3.next();
143 if ( p.n != q.n && points.get(q).contains( s ) ) {
144 if ( s instanceof Line )
145 graph[p.n][q.n] = graph[q.n][p.n] = MyMath.linearDistance( p, q );
146 else
147 graph[p.n][q.n] = graph[q.n][p.n] = MyMath.arcLength( (Circle)s, p, q );
148 }
149 }
150 }
151 }
152 for ( int k = 0; k < N; k++ )
153 for ( int i = 0; i < N; i++ )
154 for ( int j = 0; j < N; j++ )
155 graph[i][j] = Math.min( graph[i][j], graph[i][k] + graph[k][j] );
156
157 double m = 0;
158 int a = 0, b = 0;
159 for ( int i = 0; i < N; i++ )
160 for ( int j = 0; j < N; j++ )
161 if ( !MyMath.isInfinite( graph[i][j] ) && graph[i][j] > m ) {
162 a = i;
163 b = j;
164 m = graph[i][j];
165 }
166 statusLabel.setText( String.format( "Case #%d: %f", ++caseNumber, m ) );
167 maze.addFarPoints( pointsById[a].x, pointsById[a].y, pointsById[b].x, pointsById[b].y );
168
169 }
170 }
171 }
172
173 static void addPoint( Point p, Object s ) {
174 HashSet<Object> on;
175 if ( points.containsKey( p ) )
176 on = points.get( p );
177 else {
178 p = new Point( points.size(), p );
179 on = new HashSet<Object>();
180 }
181 on.add( s );
182 points.put( p, on );
183 }
184
185 }
186
187 class MazeVisualizer extends Component implements ComponentListener {
188
189 private Dimension displaySize;
190 private Point2D.Double userLowerLeft, userUpperRight;
191 ArrayList<Shape> shapes;
192 ArrayList<Point2D.Double> points;
193 Point2D.Double farP1, farP2;
194 boolean showFarPoints = false;
195
196 public MazeVisualizer( int dWidth, int dHeight, double xMin, double yMin, double xMax, double yMax ) {
197 displaySize = new Dimension( dWidth, dHeight );
198 userLowerLeft = new Point2D.Double( xMin, yMin );
199 userUpperRight = new Point2D.Double( xMax, yMax );
200 shapes = new ArrayList<Shape>( 25 );
201 points = new ArrayList<Point2D.Double>( 500 );
202 addComponentListener( this );
203 }
204
205 public void addShape( Shape s ) {
206 shapes.add( s );
207 repaint();
208 }
209
210 public void addLine( double x1, double y1, double x2, double y2 ) {
211 addShape( new Line2D.Double( x1, y1, x2, y2 ) );
212 }
213
214 public void addCircle( double x, double y, double r ) {
215 addShape( new Ellipse2D.Double( x - r, y - r, 2 * r, 2 * r ) );
216 }
217
218 public void addPoint( double x, double y ) {
219 points.add( new Point2D.Double( x, y ) );
220 repaint();
221 }
222
223 public void addFarPoints( double x1, double y1, double x2, double y2 ) {
224 farP1 = new Point2D.Double( x1, y1 );
225 farP2 = new Point2D.Double( x2, y2 );
226 showFarPoints = true;
227 repaint();
228 }
229
230 public void clearShapes() {
231 shapes = new ArrayList<Shape>( 25 );
232 points = new ArrayList<Point2D.Double>( 500 );
233 showFarPoints = false;
234 repaint();
235 }
236
237 public Dimension getPreferredSize() {
238 return displaySize;
239 }
240
241 private void setUserCoordinates( Graphics2D g2d ) {
242 double mx = getWidth() / ( userUpperRight.getX() - userLowerLeft.getX() );
243 double my = getHeight() / ( userLowerLeft.getY() - userUpperRight.getY() );
244 g2d.transform( new AffineTransform( mx, 0, 0, my, -mx * userLowerLeft.getX(), -my * userUpperRight.getY() ) );
245 }
246
247 private float pixelSize() {
248 return (float) ( userUpperRight.getX() - userLowerLeft.getX() ) / getWidth();
249 }
250
251 private void drawAxes( Graphics2D g2d, double min, double max, double arrowRotDeg, double arrowLen, Stroke stroke, Color color ) {
252 g2d.setStroke( stroke );
253 g2d.setColor( color );
254 g2d.draw( new Line2D.Double( min, 0, max, 0 ) );
255 g2d.draw( new Line2D.Double( 0, min, 0, max ) );
256 }
257
258 private void drawGrid( Graphics2D g2d, double min, double max, double step, Stroke stroke, Color color ) {
259 g2d.setStroke( stroke );
260 g2d.setColor( color );
261 double p = min;
262 while ( p <= max ) {
263 g2d.draw( new Line2D.Double( min, p, max, p ) );
264 g2d.draw( new Line2D.Double( p, min, p, max ) );
265 p += step;
266 }
267 }
268
269 public void paint( Graphics g ) {
270 Graphics2D g2d = (Graphics2D)g;
271 setUserCoordinates( g2d );
272 drawGrid( g2d, 0, 100, 10, new BasicStroke( pixelSize() ), Color.LIGHT_GRAY );
273 drawAxes( g2d, -5, 105, 30, 3, new BasicStroke( 3 * pixelSize(), BasicStroke.CAP_ROUND, BasicStroke.JOIN_ROUND ), Color.GRAY );
274 g2d.setStroke( new BasicStroke( 3 * pixelSize() ) );
275 for ( int i = 0; i < shapes.size(); i++ ) {
276 Shape s = shapes.get(i);
277 if ( s instanceof Line2D ) {
278 g2d.setColor( Color.BLUE );
279 }
280 else if ( s instanceof Ellipse2D ) {
281 g2d.setColor( Color.MAGENTA );
282 }
283 else {
284 g2d.setColor( Color.RED );
285 }
286 g2d.draw( shapes.get(i) );
287 }
288 g2d.setStroke( new BasicStroke( pixelSize() ) );
289 g2d.setColor( Color.CYAN );
290 for ( int i = 0; i < points.size(); i++ ) {
291 Point2D.Double p = points.get(i);
292 g2d.fill( new Ellipse2D.Double( p.getX() - 0.75, p.getY() - 0.75, 1.5, 1.5 ) );
293 }
294 if ( showFarPoints ) {
295 g2d.setStroke( new BasicStroke( pixelSize() ) );
296 g2d.setColor( Color.RED );
297 g2d.fill( new Ellipse2D.Double( farP1.getX() - 1.5, farP1.getY() - 1.5, 3, 3 ) );
298 g2d.fill( new Ellipse2D.Double( farP2.getX() - 1.5, farP2.getY() - 1.5, 3, 3 ) );
299 }
300 }
301
302 public void componentResized( ComponentEvent e ) {
303 int width = getWidth();
304 int height = getHeight();
305 if ( width != height ) {
306 int setTo = width < height ? width : height;
307 setSize( setTo, setTo );
308 }
309 }
310
311 public void componentMoved(ComponentEvent e) {
312 }
313
314 public void componentShown(ComponentEvent e) {
315 }
316
317 public void componentHidden(ComponentEvent e) {
318 }
319
320 }
321
322 class Edge {
323 public double x1, y1, x2, y2, w;
324 public Edge( double x1, double y1, double x2, double y2, double w ) {
325 this.x1 = x1; this.y1 = y1; this.x2 = x2; this.y2 = y2; this.w = w;
326 }
327 }
328
329 class Line {
330 public int x1, y1, x2, y2;
331 public Line( int x1, int y1, int x2, int y2 ) { this.x1 = x1; this.y1 = y1; this.x2 = x2; this.y2 = y2; }
332 }
333
334 class Circle {
335 public int x, y, r;
336 public Circle( int x, int y, int r ) { this.x = x; this.y = y; this.r = r; }
337 }
338
339 class Point {
340 int n;
341 public double x, y;
342 public Point( double x, double y ) { this.x = x; this.y = y; }
343 public Point( int n, Point p ) { this.n = n; this.x = p.x; this.y = p.y; }
344 }
345
346 class PointComparator implements Comparator<Point> {
347 public int compare( Point a, Point b ) {
348 if ( MyMath.ltDouble( a.x, b.x ) )
349 return -1;
350 else if ( MyMath.gtDouble( a.x, b.x ) )
351 return 1;
352 else {
353 if ( MyMath.ltDouble( a.y, b.y ) )
354 return -1;
355 else if ( MyMath.gtDouble( a.y, b.y ) )
356 return 1;
357 else
358 return 0;
359 }
360 }
361 }
362
363 class MyMath {
364
365 public static final double EPSILON = 1E-8;
366 public static final double INFINITY = 1E+8;
367
368 public static boolean eqDouble( double a, double b ) { return a >= b - EPSILON && a <= b - EPSILON; }
369
370 public static boolean ltDouble( double a, double b ) { return b - a > EPSILON; }
371
372 public static boolean gtDouble( double a, double b ) { return a - b > EPSILON; }
373
374 public static boolean isInfinite( double a ) { return !ltDouble( a, INFINITY ); }
375
376 public static Point xLineLine( Line l1, Line l2 ) {
377 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;
378 int d = ( y4 - y3 ) * ( x2 - x1 ) - ( x4 - x3 ) * ( y2 - y1 );
379 if ( d == 0 ) return null;
380 double a = ( ( x4 - x3 ) * ( y1 - y3 ) - ( y4 - y3 ) * ( x1 - x3 ) ) / (double)d;
381 double b = ( ( x2 - x1 ) * ( y1 - y3 ) - ( y2 - y1 ) * ( x1 - x3 ) ) / (double)d;
382 if ( a < 0 || a > 1 || b < 0 || b > 1 ) return null;
383 return new Point( x1 + a * ( x2 - x1 ), y1 + a * ( y2 - y1 ) );
384 }
385
386 public static ArrayList<Point> xLineCircle( Line l, Circle c ) {
387 int dx = l.x2 - l.x1;
388 int dy = l.y2 - l.y1;
389 int A = dx * dx + dy * dy;
390 int B = 2 * ( dx * ( l.x1 - c.x ) + dy * ( l.y1 - c.y ) );
391 int C = ( l.x1 - c.x ) * ( l.x1 - c.x ) + ( l.y1 - c.y ) * ( l.y1 - c.y ) - c.r * c.r;
392 int D = B * B - 4 * A * C;
393 if ( D == 0 )
394 System.err.format( ">>Tangent? L %d %d %d %d, C %d %d %d%n", l.x1, l.y1, l.x2, l.y2, c.x, c.y, c.r );
395 if ( D < 0 ) return null;
396 ArrayList<Point> points = new ArrayList<Point>( 2 );
397 double t = ( -B + Math.sqrt( D ) ) / ( 2 * A );
398 if ( t >= 0 && t <= 1 ) {
399 points.add( new Point( l.x1 + t * dx, l.y1 + t * dy ) );
400 if ( t < 0.001 || t > 0.999 )
401 System.err.format( ">>Degenerate? L %d %d %d %d, C %d %d %d%n", l.x1, l.y1, l.x2, l.y2, c.x, c.y, c.r );
402 }
403 t = ( -B - Math.sqrt( D ) ) / ( 2 * A );
404 if ( t >= 0 && t <= 1 ) {
405 points.add( new Point( l.x1 + t * dx, l.y1 + t * dy ) );
406 if ( t < 0.001 || t > 0.999 )
407 System.err.format( ">>Degenerate? L %d %d %d %d, C %d %d %d%n", l.x1, l.y1, l.x2, l.y2, c.x, c.y, c.r );
408 }
409 return points;
410 }
411
412 public static ArrayList<Point> xCircleCircle( Circle c1, Circle c2 ) {
413 if ( c1.x == c2.x && c1.y == c2.y && c1.r == c2.r )
414 System.err.format( ">>Degenerate? C %d %d %d, C %d %d %d%n", c1.x, c1.y, c1.r, c2.x, c2.y, c2.r );
415 int dx = c2.x - c1.x;
416 int dy = c2.y - c1.y;
417 double d = Math.sqrt( dx * dx + dy * dy );
418 if ( d > c1.r + c2.r || d < Math.abs( c1.r - c2.r ) ) return null;
419 double a = ( c1.r * c1.r - c2.r * c2.r + d * d ) / ( 2 * d );
420 double x = c1.x + dx * a / d;
421 double y = c1.y + dy * a / d;
422 double h = Math.sqrt( c1.r * c1.r - a * a );
423 double rx = -dy * h / d;
424 double ry = dx * h / d;
425 ArrayList<Point> points = new ArrayList<Point>( 2 );
426 if ( Math.abs( rx ) < 0.001 && Math.abs( ry ) < 0.001 )
427 System.err.format( ">>Degenerate? C %d %d %d, C %d %d %d%n", c1.x, c1.y, c1.r, c2.x, c2.y, c2.r );
428 points.add( new Point( x + rx, y + ry ) );
429 points.add( new Point( x - rx, y - ry ) );
430 return points;
431 }
432
433 public static double linearDistance( Point p, Point q ) {
434 return Math.sqrt( ( p.x - q.x ) * ( p.x - q.x ) + ( p.y - q.y ) * ( p.y - q.y ) );
435 }
436
437 public static double arcLength( Circle c, Point p, Point q ) {
438 double theta = Math.abs( Math.atan2( p.y - c.y, p.x - c.x ) - Math.atan2( q.y - c.y, q.x - c.x ) );
439 return c.r * Math.min( theta, 2 * Math.PI - theta );
440 }
441
442 }