import java.io.*; import java.util.*; import java.awt.geom.*; /** * Solution to Triangles * * We'll use a 'rotating calipers' style solution. * * Start by sorting the points by X coordinate. Now, consider two points that form a vertical line. * We'll consider other cases later. Those two points form a line segment that could be the base * of a triangle. With that base, what's the largest triangle you could form? It's formed by the point * which has the greatest distance from that line. Since that line is vertical, that's the point with * the most distance X coordinate. We've sorted by X, so that's either the first point, or the last point, * in the list! How about the smallest triangle? That'll be formed by one of the points closest to these points. * So, look at the sorted points immediately before & after the endpoints in the sorted array, and it has to be * one of them! Because we're looking at a vertical line, the points sorted by X coordinate are also sorted by * distance from any vertical line! * * That's great for vertical line segments, but what about others? Think about two points that form a line * that's close to vertical, but not quite. Let them be the two points whose angle is closest * to vertical of all pairs of points. Rotate the whole system so that they ARE vertical. (In * our solution, we won't actually do this, it's just for explanation). Look at the sorted array of points. * Since these two were the closest to vertical, if we look at the sort order as distance from the line, * none of the other points will change position in the sorted array. So, our argument about min/max * above still holds. Suppose we rotate just a little bit more. The only points to change positions are the * two points we're considering! * * So, that's our strategy. Sort the points by X. Create all possible line segments from pairs * of points, sort them by angle. Go through the lines in order, looking in the sorted points array * for min/max. Then, swap the two points, and it's on to the next line. * * @author vanb */ public class triangles_vanb { public Scanner sc; public PrintStream ps; /** * A point. * * @author vanb */ public class Point implements Comparable { // [x,y] position, index into an array of Points public int x, y, index; public Point( int x, int y ) { this.x=x; this.y=y; index = 0; } /** * Compare two points by x, then y. * * @param p A point to compare to this one * @return -1, 0 or 1, as per usual for compareTo() */ public int compareTo( Point p ) { int diff = x-p.x; if( diff==0 ) diff = y-p.y; return diff; } /** * Determine of two points are equal * * @param p Another Point * @return true if p==this, otherwise false */ public boolean equals( Point p ) { return x==p.x && y==p.y; } /** * A Pretty String for debugging * * @return A Pretty String */ public String toString() { return "(" + x + "," + y + ")"; } } /** * A Line Segment * * @author vanb */ public class Line implements Comparable { // Endpoints of the segment public Point p1, p2; // Angle from p1 to p2 public double angle; /** * Create a Line * * @param p1 One Endpoint * @param p2 Another Endpoint */ public Line( Point p1, Point p2 ) { this.p1 = p1; this.p2 = p2; angle = Math.atan2( p2.x-p1.x, p2.y-p1.y ); } /** * Compare this Line to another, based on angle * * @param line Another line * @return -1, 0 or 1, as per usual for compareTo() */ public int compareTo( Line line ) { return Double.compare( angle, line.angle ); } /** * A Pretty String for debugging * * @return A Pretty String */ public String toString() { return "" + p1 + "-" + p2; } /** * Determine if a point is one of the endpoints of this Line. * * @param p A point * @return true if p is an endpoint of this line, otherwise fals */ public boolean contains( Point p ) { return p1.equals( p ) || p2.equals( p ); } } /** * Distance between two points. * * @param p1 A Point * @param p2 Another Point * @return Distance from p1 to p2 */ public double distance( Point p1, Point p2 ) { return Math.hypot( p2.y-p1.y, p2.x-p1.x ); } /** * Are of a triangle, given its three points, via Heron's formula. * * @param p1 A corner of the triangle * @param p2 Another corner of the triangle * @param p3 Yet another corner of the triangle * @return Area of triangle p1-p2-p3 */ public double heron( Point p1, Point p2, Point p3 ) { double area = Double.MAX_VALUE; double a = distance( p1, p2 ); double b = distance( p1, p3 ); double c = distance( p3, p2 ); double s = (a+b+c)/2.0; area = Math.sqrt( s*(s-a)*(s-b)*(s-c) ); return area; } /** * Driver. * @throws Exception */ public void doit() throws Exception { sc = new Scanner( System.in ); //new File( "triangles.judge" ) ); ps = System.out; //new PrintStream( new FileOutputStream( "triangles.solution" ) ); for(;;) { int n = sc.nextInt(); if( n==0 ) break; Point points[] = new Point[n]; for( int i=0; ilargest ) largest = area; } if( !line.contains( points[0] ) ) { area = heron( line.p1, line.p2, points[0] ); if( area>largest ) largest = area; } // Look at the closest points to find the smallest triangle. int index1 = line.p1.index; int index2 = line.p2.index; if( index1>0 && !line.contains(points[index1-1]) ) { area = heron( line.p1, line.p2, points[index1-1] ); if( area0 && !line.contains(points[index2-1]) ) { area = heron( line.p1, line.p2, points[index2-1] ); if( area