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 }