import java.io.PrintStream; import java.util.Arrays; import java.util.Scanner; /** * Solution to Dorm Room Divide */ public class dorm_vanb { /** The input. */ private static Scanner sc; /** The output. */ private static PrintStream ps; private static final double EPSILON = 1e-7; /** * Area of a triangle with vertices (x1,y1), (x2,y2) and (x3,y3) * * @param x1 * @param y1 * @param x2 * @param y2 * @param x3 * @param y3 * @return Area */ private static double triarea( double x1, double y1, double x2, double y2, double x3, double y3 ) { return Math.abs( (x2-x1)*(y2+y1) + (x3-x2)*(y3+y2) + (x1-x3)*(y1+y3) )/2.0; } /** * Do it. */ private void doit() { int n = sc.nextInt(); double xs[] = new double[n]; double ys[] = new double[n]; for( int i=0; iP1-->Pi-->P0 // for every i from 3 to n-1 double areas[] = new double[n]; areas[0] = areas[1] = 0.0; double area = (xs[1]-xs[0])*(ys[1]+ys[0])/2.0; for( int i=2; i=0 ) { x = xs[index]; y = ys[index]; } else { index = -(index+1); double hix = xs[index]; double hiy = ys[index]; double lox = xs[index-1]; double loy = ys[index-1]; double doorx = xs[0]; double doory = ys[0]; double basex = lox; double basey = loy; for(;;) { double midx = (lox+hix)/2.0; double midy = (loy+hiy)/2.0; double areamid = triarea( doorx, doory, basex, basey, midx, midy )+areas[index-1]; System.err.println( midx + " " + midy + " " + areamid + " " + half ); if( Math.abs( areamid-half )