import java.io.*; import java.util.*; import java.text.*; import java.awt.geom.*; class levees_judge { public Scanner sc; public PrintStream ps; public String toString() { return "levees_judge"; } // Distance between two points public double distance( double x1, double y1, double x2, double y2 ) { double dx = x2-x1; double dy = y2-y1; return Math.sqrt( dx*dx + dy*dy ); } // Compute the area and perimeter of a triangle, given its points // Return a 2-tuple of ( area, perimeter ) public Point2D triangle( double x1, double y1, double x2, double y2, double x3, double y3 ) { // Length of sides double a = distance( x1, y1, x2, y2 ); double b = distance( x2, y2, x3, y3 ); double c = distance( x3, y3, x1, y1 ); // Perimeter is the sum of the sides double perimeter = a+b+c; // This is Heron's formula for area double s = perimeter/2.0; double area = Math.sqrt( s*(s-a)*(s-b)*(s-c) ); return new Point2D.Double( area, perimeter ); } // Check to see if a value is close enough to be considered 0 public boolean iszero( double x ) { return Math.abs(x)<0.00001; } public void doit() throws Exception { sc = new Scanner( System.in ); ps = System.out; DecimalFormat df = new DecimalFormat( "0.000" ); for(;;) { // Read the points double x1 = sc.nextDouble(); double y1 = sc.nextDouble(); double x2 = sc.nextDouble(); double y2 = sc.nextDouble(); double x3 = sc.nextDouble(); double y3 = sc.nextDouble(); double x4 = sc.nextDouble(); double y4 = sc.nextDouble(); // The problem promises that no two points will be the same. // So, if (x1,y1)==(0,0) and (x2,y2)==(0,0), then we have to be // at the end of the input, No need to check x3,y3,x4,y4. if( iszero(x1) && iszero(y1) && iszero(x2) && iszero(y2) ) break; // Find point of intersection of the two diagonals using Cramer's rule. // We're guaranteed that the line segments intersect, because the input points are // guaranteed to form a convex quadrilateral. So, if we look at the lines which go // through those segments, they're guaranteed to intersect inside the figure. We'll // find that point of intersection with Cramer's rule. // Express each line in the form ax + by = c // First, the (x1,y1)-(x3,y3) diagonal // Remember that a line can be expressed as y=m*x+b, where m=slope. // That means, in this case, m = (y3-y1)/(x3-x1). Well, with a little algebra, // that means that (x3-x1)*y - (y3-y1)*x = K (K is some constant) // A little more algebra leads to (y3-y1)*x + (x1-x3)*y = C (C is another constant). // So, in the form ax + by = c, a=(y3-y1), b=(x1-x3). // We can get c by plugging in one of the points. So, c = a*x1 + b*y1 double a1 = y1-y3; double b1 = x3-x1; double c1 = a1*x1 + b1*y1; // Now, the (x2,y2)-(x4,y4) diagonal // Same math holds here. double a2 = y2-y4; double b2 = x4-x2; double c2 = a2*x2 + b2*y2; // Now, for Cramer's Rule. // // It says that if you have two linear equations: // a1*x + b1*y = c1 and // a2*x + b2*y = c2 // // If they intersect at a single point (and, in this problem, that's guaranteed), then // you can compute the point of intersection like this: // // | a1 b1 | // Let D = | | // | a2 b2 | // // | c1 b1 | | a1 c1 | // | | | | // Then x = | c2 b2 | And y = | a2 c2 | // ---------- ---------- // D D // // Remember also the determinant of a 2x2 matrix: // // | w x | // | | = w*z - y*x // | y z | // // Then, it all simplifies to this: // // c1*b2 - c2*b1 a1*c2 - a2*c1 // x = ------------- y = ------------- // a1*b2 - a2*b1 a1*b2 - a2*b1 // // So, this will give us (x5,y5), the point in the middle which is common to // all four triangular areas. double d = a1*b2 - a2*b1; double x5 = (c1*b2 - c2*b1)/d; double y5 = (a1*c2 - a2*c1)/d; // OK, now get the fours areas and perimeters Point2D areas[] = new Point2D[4]; areas[0] = triangle( x1, y1, x2, y2, x5, y5 ); areas[1] = triangle( x2, y2, x3, y3, x5, y5 ); areas[2] = triangle( x3, y3, x4, y4, x5, y5 ); areas[3] = triangle( x4, y4, x1, y1, x5, y5 ); // Sort them with a simple selection sort for( int i=0; i<4; i++ )for( int j=i+1; j<4; j++ ) { double ai = areas[i].getX(); String si = df.format( ai ); double pi = areas[i].getY(); double aj = areas[j].getX(); String sj = df.format( aj ); double pj = areas[j].getY(); // Two areas are compared not as is, but rounded to three decimal places. // That's why we need to compare si and sj if( (si.equals(sj) && pj>pi) || (!si.equals(sj) && aj>ai) ) { Point2D temp = areas[i]; areas[i] = areas[j]; areas[j] = temp; } } // And, print them. boolean first = true; String pad = ""; for( int i=0; i<4; i++ ) { ps.printf( "%s%.3f %.3f", pad, areas[i].getX(), areas[i].getY() ); if( first ) { pad = " "; first = false; } } ps.println(); } } public static void main(String[] args) throws Exception { new levees_judge().doit(); } }