The Java Program: D_angles/equalangles.java

  1 
  2 
  3 import java.awt.geom.*;
  4 import java.awt.*;
  5 import java.io.*;
  6 import java.util.*;
  7 
  8 public class equalangles 
  9 {
 10     public Scanner sc;
 11     public PrintStream ps;
 12     
 13     public static final double epsilon = 0.00000001;
 14     
 15     /**
 16      * Distance between two points.
 17      * 
 18      * @param x1 X coord of first point
 19      * @param y1 Y coord of first point
 20      * @param x2 X coord of second point
 21      * @param y2 Y coord of second point
 22      * @return The distance between (x1,y1) and (x2,y2)
 23      */
 24     public double distance( double x1, double y1, double x2, double y2 )
 25     {
 26         double dx = x2-x1;
 27         double dy = y2-y1;
 28         
 29         return Math.sqrt( dx*dx + dy*dy );
 30     }
 31     
 32     /**
 33      * Use the Law of Cosines to compute an angle of a triangle, given its side lengths.
 34      * 
 35      * Given the lengths of three sides of a triangle a, b and c, and an angle theta which is adjacent
 36      * to a and b (opposite c), then the Law of Cosines sez:
 37      * 
 38      *         c^2 = a^2 + b^2 - 2*a*b*cos(theta)
 39      *         
 40      * So, if you know any three of the parameters, you can compute the fourth with
 41      * just a little algebra.
 42      * 
 43      * Interesting to note: if theta is 90 degrees, then you've got a right triangle
 44      * with c as the hypotenuse. Since cos(90 degrees)=0, the Law of Cosines reduces
 45      * to the Pythagorean Theorem.
 46      * 
 47      * @param a Length of a side adjacent to the angle
 48      * @param b Length of a side adjacent to the angle
 49      * @param c Length of the side opposite the angle
 50      * @return The angle
 51      */
 52     public double angle( double a, double b, double c )
 53     {
 54         return Math.acos( ( a*a + b*b - c*c ) / ( 2.0*a*b ) );
 55     }
 56     
 57     /**
 58      * Use the Law of Cosines to compute the length of a side of a triangle,
 59      * given the lengths of the other two sides and the opposite angle.
 60      * 
 61      * See 'angle()' for s description of the Law of Cosines.
 62      * 
 63      * @param a Length of a side
 64      * @param b Length of a side
 65      * @param theta Angle opposite the third side
 66      * @return Length of the third side
 67      */
 68     public double side( double a, double b, double theta )
 69     {
 70         return Math.sqrt( a*a + b*b - 2.0*a*b*Math.cos(theta) );
 71     }
 72     
 73     /**
 74      * Use the Law of Sines to compute the length of a side of a triangle,
 75      * given the opposite angle, and another side, and the angle opposite that side.
 76      * 
 77      * If a, b and c are the lengths of the sides of a triangle, and A, B and C are
 78      * the angles at the points OPPOSITE a, b and c (i.e. A is opposite a, etc.)
 79      * then the Law of Sines sez:
 80      * 
 81      *         sin(A)/a = sin(B)/b = sin(C)/c
 82      *         
 83      * So, if you know A, a and B, you can easily compute b as sin(B) * a / sin(B)
 84      *  
 85      * @param t1 Angle opposite the known side
 86      * @param a1 The length of the known side
 87      * @param t2 The angle opposite the unknown side
 88      * @return The length of the unknown side
 89      */
 90     public double sines( double t1, double a1, double t2 )
 91     {
 92         return Math.sin( t2 ) * a1 / Math.sin( t1 );
 93     }
 94     
 95     /**
 96      * Compute the point P, for which angles PAB, PBC, and PCA are all equal.
 97      * 
 98      * @param ax X coord of A
 99      * @param ay Y coord of A
100      * @param bx X coord of B
101      * @param by Y coord of B
102      * @param cx X coord of C
103      * @param cy Y coord of C
104      * @return The point (px,py)
105      */
106     public Point2D.Double anglepoint( double ax, double ay, double bx, double by, double cx, double cy )
107     {
108         // Use the distance formula to get the lengths of the sides
109         double ab = distance( ax, ay, bx, by );
110         double bc = distance( bx, by, cx, cy );
111         double ca = distance( cx, cy, ax, ay );
112         
113         // Use the Law of Cosines to get the angles at each point
114         double a = angle( ca, ab, bc );
115         double b = angle( ab, bc, ca );
116         double c = angle( bc, ca, ab );
117         
118         // We need to find a point P such that angles PAB, PBC and PCA are all equal.
119         // We'll take a guess at that angle, and fix that guess angle on points A and B. 
120         // We'll see what angle the point of intersection forms with C (call that angle theta).
121         // We'll then use the bisection method to find the root of the function guess-theta.
122         //
123         // It is interesting to note that we can do all of this without actually finding
124         // the point P!
125         double lo = 0.0;
126         double hi = Math.min( Math.min( a, b ), c );
127         double theta = 0.0;
128         double pa = 0.0, pb = 0.0, pc = 0.0;
129         while( hi-lo > epsilon )
130         {
131                 // This is the guess
132                 double mid = (hi+lo)/2.0;
133                 
134                 // In the triangle PAB, find the length of side PA using the Law of Sines.
135                 // Note that angle APB is pi-b, no matter what the guess is!
136                 // That's because PAB = guess, ABP = B-guess, and the three angles of
137                 // a triangle always total pi, so APB = pi - guess - (B-guess) = pi - B.
138             pa = sines( Math.PI-b, ab, b-mid );
139             
140             // Ditto finding the length of side PB using the Law of Sines with triangle PAB
141             pb = sines( Math.PI-b, ab, mid );
142             
143             // To find the length of side PC, we'll use the Law of Cosines with triangle PBC. 
144             pc = side( pb, bc, mid );
145             
146             // And finally, we'll find our angle theta using the Law of Cosines with triangle PCA.
147                 theta = angle( ca, pc, pa );
148                 
149                 // And here's the bisection method.
150                 if( mid-theta<0.0 )
151                 {
152                         lo = mid;
153                 }
154                 else
155                 {
156                         hi = mid;
157                 }
158         }
159         
160         // OK, we know theta, but we got it without computing P.
161         // Now, we have to compute P!
162         //
163         // Start by figuring the angle from A to B
164         double a2b = Math.atan2( by-ay, bx-ax );
165         
166         // Now, we don't know whether the points were given clockwise 
167         // or counterclockwise. We'll take a guess, and see if P is
168         // inside or outside the triangle. If it's outside, then we guessed wrong.
169         // We'll start by guessing Clockwise.
170         double alpha = a2b + theta;
171         
172         // Shoot a ray from point a through p, out past the triangle.
173         // If it crosses line segment bc, then P must be in the triangle.
174         double testlen = Math.max( ab, ca ) + 10.0; 
175         double tx = ax + testlen*Math.cos( alpha );
176         double ty = ay + testlen*Math.sin( alpha );
177         
178         // If the line segments don't intersect, then we guessed wrong.
179         if( !Line2D.Double.linesIntersect( ax, ay, tx, ty, bx, by, cx, cy ) )
180         {
181                 // OK, it's counterclockwise, which means we have to subtract theta.
182                 alpha = a2b - theta;
183         }
184         double px = ax + pa*Math.cos( alpha );
185         double py = ay + pa*Math.sin( alpha );         
186         
187         return new Point2D.Double( px, py );
188     }
189        
190     /**
191      * The driver.
192      * 
193      * @throws Exception
194      */
195     public void doit() throws Exception
196     {
197         sc = new Scanner( new File( "equalangles.judge" ) );
198         ps = new PrintStream( new FileOutputStream( "equalangles.out" ) ); 
199         
200         for(;;)
201         {
202             double ax = sc.nextDouble();
203             double ay = sc.nextDouble();
204             double bx = sc.nextDouble();
205             double by = sc.nextDouble();
206             double cx = sc.nextDouble();
207             double cy = sc.nextDouble();
208        
209             // We're guaranteed that the triangle isn't pathological or trivial.
210             // So, if the length of side AB is zero, we must be at the end of the data.
211             if( distance( ax, ay, bx, by ) < epsilon  ) break;
212             
213             Point2D.Double p = anglepoint( ax, ay, bx, by, cx, cy );
214             Point2D.Double q = anglepoint( ax, ay, cx, cy, bx, by );
215             
216             ps.printf( "%.2f %.2f %.2f %.2f", p.x, p.y, q.x, q.y );  
217             ps.println();
218             System.out.printf( "%.2f %.2f %.2f %.2f", p.x, p.y, q.x, q.y );  
219             System.out.println();
220         }
221     }
222     
223     public boolean eq( int x1, int y1, int x2, int y2 )
224     {
225         return x1==x2 && y1==y2;
226     }
227     
228     public void div10() throws Exception
229     {
230         sc = new Scanner( new File( "equalangles.in" ) );
231         ps = new PrintStream( new FileOutputStream( "equalangles.out" ) ); 
232         
233         for(;;)
234         {
235             int ax = sc.nextInt()/10;
236             int ay = sc.nextInt()/10;
237             int bx = sc.nextInt()/10;
238             int by = sc.nextInt()/10;
239             int cx = sc.nextInt()/10;
240             int cy = sc.nextInt()/10;
241             
242             //if( ax==0 && ay==0 && bx==0 && by==0 ) break;
243             
244             if( eq(ax,ay,bx,by) || eq(ax,ay,cx,cy) || eq(bx,by,cx,cy) )
245             {
246                 System.out.println( "ACK! " + ax + " " + ay + " " + bx + " " + by + " " + cx + " " + cy);
247             }
248             else
249             {
250                 System.out.println( ax + " " + ay + " " + bx + " " + by + " " + cx + " " + cy );
251             }
252        
253         }
254     }
255     
256     public static void printcase( Point a, Point b, Point c )
257     {
258         if( !a.equals( b ) && !a.equals( b ) && !b.equals( c ) )
259         {
260             System.out.println( a.x + " " + a.y + " " + b.x + " " + b.y + " " + c.x + " " + c.y );
261         }
262     }
263     
264     public static void printallcases( int ax, int ay, int bx, int by, int cx, int cy )
265     {
266         Point a = new Point( ax, ay );
267         Point b = new Point( bx, by );
268         Point c = new Point( cx, cy );
269         printcase( a, b, c );   
270         printcase( b, c, a );   
271         printcase( c, a, b );   
272         printcase( a, c, b );   
273         printcase( b, a, c );   
274         printcase( c, b, a );   
275     }
276     
277     public static Random random = new Random();
278     
279     public static int r()
280     {
281         return random.nextInt( 2001 ) - 1000;
282     }
283     
284     /**
285      * The main, which just creates an object and calls doit().
286      * 
287      * @param args Command line args - necessary, but unused.
288      * @throws Exception
289      */
290         public static void main( String[] args ) throws Exception
291         {
292         new equalangles().doit();
293             //printallcases( -100, 0, -99, 0, 100, 1 );
294         //new equalangles().div10();
295 //          printallcases( -4, 5, -10, 0, 7, 0 );
296 //          printallcases( -15, -5, 15, -5, 0, 21 );
297 //          printallcases( 0, 0, 36, 24, 48, 0 );
298 //        printallcases( 0, 0, 0, 500, 900, 0 );
299 //        printallcases( 0, 0, 0, -500, 900, 0 );
300 //        printallcases( 0, 0, 0, 500, -900, 0 );
301 //        printallcases( 0, 0, 0, -500, -900, 0 );
302 //        printallcases( 1000, 1000, 1000, -1000, -1000, -1000 );
303 //        for( int i=0; i<20; i++ )
304 //        {
305 //            printallcases( r(), r(), r(), r(), r(), r() );
306 //        }         
307         }
308 
309 }