The Java Program: B_euclid/euclid.java

  1 import java.io.*;
  2 import java.util.*;
  3 import java.awt.*;
  4 import java.awt.geom.*;
  5 import java.text.*;
  6 import java.math.*;
  7 
  8 /**
  9  * Solution to Euclid 
 10  * 
 11  * This version finds a closed-form solution, using mainly trig.
 12  */
 13 class euclid
 14 {
 15     public Scanner sc;
 16     public PrintStream ps;
 17 
 18     public String toString()
 19     {
 20         return "euclid";
 21     }
 22     
 23     /**
 24      * Determine if a double is sufficiently close to zero to be considered zero.
 25      * 
 26      * @param x A double to check
 27      * @return true if x is sufficiently close to zero, otherwise false.
 28      */
 29     public boolean z( double x )
 30     {
 31         return x>-0.000001 && x<0.000001;
 32     }
 33     
 34     /**
 35      * Distance between points (x1,y1) and (x2,y2).
 36      * 
 37      * @param x1
 38      * @param y1
 39      * @param x2
 40      * @param y2
 41      * @return The distance between the points
 42      */
 43     public double dist( double x1, double y1, double x2, double y2 )
 44     {
 45         double dx = x2-x1;
 46         double dy = y2-y1;
 47         return Math.sqrt( dx*dx + dy*dy );
 48     }
 49     
 50     /**
 51      * Compute the area of triangle (x1,y1)-(x2,y2)-(x3,y3) using Heron's formula.
 52      * 
 53      * @param x1
 54      * @param y1
 55      * @param x2
 56      * @param y2
 57      * @param x3
 58      * @param y3
 59      * @return The area of the triangle.
 60      */
 61     public double heron( double x1, double y1, double x2, double y2, double x3, double y3 )
 62     {
 63         double d1 = dist( x1, y1, x2, y2 );
 64         double d2 = dist( x2, y2, x3, y3 );
 65         double d3 = dist( x1, y1, x3, y3 );
 66         
 67         double s = (d1 + d2 + d3) / 2.0;
 68         
 69         return Math.sqrt( s * (s-d1) * (s-d2) * (s-d3) );
 70     }
 71                 
 72     /**
 73      * The main method.
 74      * @throws Exception
 75      */
 76     public void doit() throws Exception
 77     {
 78         sc = new Scanner( System.in ); // new Scanner( new File( "euclid.judge" ) );
 79         ps = System.out; // new PrintStream( new FileOutputStream( "euclid.solution" ) );
 80         
 81         for(;;)
 82         {
 83                 // Read in the twelve inputs
 84                 double ax = sc.nextDouble();
 85                 double ay = sc.nextDouble();
 86                 double bx = sc.nextDouble();
 87                 double by = sc.nextDouble();
 88                 double cx = sc.nextDouble();
 89                 double cy = sc.nextDouble();
 90                 double dx = sc.nextDouble();
 91                 double dy = sc.nextDouble();
 92                 double ex = sc.nextDouble();
 93                 double ey = sc.nextDouble();
 94                 double fx = sc.nextDouble();
 95                 double fy = sc.nextDouble();
 96                 
 97                 // Only need to check these six, 
 98                 // since the problem statement promises that A, B and C will
 99                 // not be collinear.
100                 if( z(ax) && z(ay) && z(bx) && z(by) && z(cx) && z(cy) ) break;
101                 
102                 // A bit of notation - if points A, B and C form a triangle, then:
103                 // Let A represent the angle at point A (same for B and C)
104                 // Let a represent the distance of the edge OPPOSITE point A.
105                 // That is, a = distance(BC), b = distance(AC), c = distance(AB).
106                 
107                 // Consider ABC to be a triangle.
108                 // Compute distances of the lines opposite the points 
109                 double c = dist( ax, ay, bx, by ); 
110                 double b = dist( ax, ay, cx, cy );
111                 double a = dist( bx, by, cx, cy );
112                 
113                 // Use the Law of Cosines to get angle A
114                 // Law of Cosines sez that a*a = b*b + c*c - 2*b*c*cos(A)
115                 // (where distances are notated as above - a is BC, b is AC and c is AB)
116                 // So, solve for cos(A), we get this:
117                 double cosine = (c*c+b*b-a*a) / (2.0*c*b);
118                                 
119                 // Use Heron's formula to get the area of triangle DEF
120                 double area = heron( dx, dy, ex, ey, fx, fy );
121                                 
122                 // Now, compute the height of the parallelogram
123                 // The area of a parallelogram is the same as that of a rectangle - base*height
124                 //        C
125                 //       /
126                 //      H--------------------G
127                 //     /|                   /
128                 //    / |                  /
129                 //   /  |height           /
130                 //  /   |                /
131                 // A----+---------------B
132                 // Well, we know the base - that's AB (length is c).
133                 double height = area / c;
134                 
135                 // Now we know the height, we have to figure out how far along
136                 // ray AC to put point H.
137                 //        C
138                 //       /
139                 //      H
140                 //     /|
141                 //    / |
142                 //   /  |height
143                 //  /   | 
144                 // A----+---------------B
145                 
146                 
147                 // Now, use the Law of Sines to get the distance along ray AC that H must be.
148                 // Law of Sines sez that in a triangle, a/sin(A) = b/sin(B) = c/sin(C).
149                 // (same notation as described above)
150                 // Well, we've got a little right triangle here. So...
151                 // 
152                 // dist(AH)/sin(pi/2) = height/sin(A)
153                 // 
154                 // Well, sin(pi/2) = 1, and sin(A) = sqrt(1-cos(A)^2)
155                 double dist = height / Math.sqrt( 1.0 - cosine*cosine );
156                 
157                 // Find how far along as a ratio
158                 double ratio = dist / b;
159                 
160                 // Now we know the diff - how far along we should go in each direction
161                 double diffx = ratio*(cx-ax);
162                 double diffy = ratio*(cy-ay);
163                 
164                 // And we know H
165                 double hx = ax + diffx;
166                 double hy = ay + diffy;
167                 
168                 // And we know G
169                 double gx = bx + diffx;
170                 double gy = by + diffy;
171                 
172                 // A little something the judges used to screen out
173                 // test cases which produced values that we considered too big.
174                 if( Math.abs(gx)<1000000.0 && Math.abs(gy)<1000000.0 
175                         && Math.abs(hx)<1000000.0 && Math.abs(hx)<1000000.0 )
176                 {
177                     ps.printf( "%.3f %.3f %.3f %.3f", gx, gy, hx, hy );
178                     ps.println();
179                 }
180                 else
181                 {
182                         ps.println( "PANIC: Results too big" );
183                 }
184         }
185     }
186     
187     public static boolean collinear( double ax, double ay, double bx, double by, double cx, double cy )
188     {
189         return Math.abs( Math.atan2(ay-by,ax-bx) - Math.atan2(by-cy,bx-cx) ) < 0.0001;
190     }
191 
192         public static void main(String[] args) throws Exception
193         {
194                 /*
195                 Point points[] = 
196                 {
197                         new Point( -1, 10),
198                         new Point( 0, 10 ),
199                         new Point( 1, 10 ),
200                         new Point( 10, 1 ),
201                         new Point( 10, 0 ),
202                         new Point( 10, -1 ),
203                         new Point( 1, -10 ),
204                         new Point( 0, -10 ),
205                         new Point( -1, -10 ),
206                         new Point( -10, -1 ),
207                         new Point( -10, 0 ),
208                         new Point( -10, 1 )
209                 };
210                 
211                 for( Point p : points ) for( Point q : points )
212                 {
213                         if( p!=q && !collinear( p.x, p.y, 0.0, 0.0, q.x, q.y ) )
214                         {
215                                 System.out.println( "0 0 " + p.x + " " + p.y + " " + q.x + " " + q.y + " 20 20 30 25 25 15" );
216                         }
217                 }
218                 
219                 Random random = new Random();
220                 
221                 for( int i=0; i<1000; i++ )
222                 {
223                     double ax = random.nextDouble()*2000.0 - 1000.0;
224                     double ay = random.nextDouble()*2000.0 - 1000.0;
225                     double bx = random.nextDouble()*2000.0 - 1000.0;
226                     double by = random.nextDouble()*2000.0 - 1000.0;
227                     double cx = random.nextDouble()*2000.0 - 1000.0;
228                     double cy = random.nextDouble()*2000.0 - 1000.0;
229                     double dx = random.nextDouble()*2000.0 - 1000.0;
230                     double dy = random.nextDouble()*2000.0 - 1000.0;
231                     double ex = random.nextDouble()*2000.0 - 1000.0;
232                     double ey = random.nextDouble()*2000.0 - 1000.0;
233                     double fx = random.nextDouble()*2000.0 - 1000.0;
234                     double fy = random.nextDouble()*2000.0 - 1000.0;
235                     if( !collinear( ax, ay, bx, by, cx, cy ) && !collinear( dx, dy, ex, ey, fx, fy ) )
236                     {
237                         System.out.printf( "%.3f %.3f %.3f %.3f %.3f %.3f %.3f %.3f %.3f %.3f %.3f %.3f", 
238                                         ax, ay, bx, by, cx, cy, dx, dy, ex, ey, fx, fy);
239                         System.out.println();
240                     }
241                 }
242                 */
243                 long starttime = System.currentTimeMillis();
244                 new euclid().doit();
245                 System.out.println( System.currentTimeMillis() - starttime );
246         }
247 }