triangles/triangles_vanb_slow.java

  1 
  2 import java.io.*;
  3 import java.util.*;
  4 import java.awt.geom.*;
  5 
  6 /**
  7  * Solution to Triangles
  8  * 
  9  * @author vanb
 10  */
 11 public class triangles_vanb_slow
 12 {
 13     public Scanner sc;
 14     public PrintStream ps;
 15     
 16     public class Point implements Comparable<Point>
 17     {
 18         public int x, y, index;
 19         
 20         public Point( int x, int y )
 21         {
 22             this.x=x; this.y=y;
 23             index = 0;
 24         }
 25         
 26         public int compareTo( Point p )
 27         {
 28             int diff = x-p.x;
 29             if( diff==0 ) diff = y-p.y;
 30             return diff;
 31         }
 32         
 33         public boolean equals( Point p )
 34         {
 35             return x==p.x && y==p.y;
 36         }
 37         
 38         public String toString()
 39         {
 40             return "(" + x + "," + y + ")";
 41         }
 42     }
 43     
 44     public class Line implements Comparable<Line>
 45     {
 46         public Point p1, p2;
 47         public double angle;
 48         
 49         public Line( Point p1, Point p2 )
 50         {
 51             this.p1 = p1;
 52             this.p2 = p2;
 53             angle = Math.atan2( p2.x-p1.x, p2.y-p1.y );
 54         }
 55         
 56         public int compareTo( Line line )
 57         {
 58             return Double.compare( angle, line.angle );
 59         }   
 60         
 61         public String toString()
 62         {
 63             return "" + p1 + "-" + p2;
 64         }
 65         
 66         public boolean contains( Point p )
 67         {
 68             return p1.equals( p ) || p2.equals( p );
 69         }
 70     }
 71     
 72     public double distance( Point p1, Point p2 )
 73     {
 74         double dx = p2.x-p1.x;
 75         double dy = p2.y-p1.y;
 76         
 77         return Math.sqrt( dx*dx + dy*dy );
 78     }
 79     public double heron( Point p1, Point p2, Point p3 )
 80     {
 81         double area = Double.MAX_VALUE;
 82         
 83         double a = distance( p1, p2 );
 84         double b = distance( p1, p3 );
 85         double c = distance( p3, p2 );
 86         
 87         if( a>0.5 && b>0.5 && c>0.5 )
 88         {
 89             double s = (a+b+c)/2.0;
 90             area = Math.sqrt( s*(s-a)*(s-b)*(s-c) );
 91         }
 92         
 93         return area;
 94     }
 95     /**
 96      * Driver.
 97      * @throws Exception
 98      */
 99     public void doit() throws Exception
100     {
101         sc = new Scanner( new File( "triangles.judge" ) );
102         ps = new PrintStream( new FileOutputStream( "triangles.test" ) );
103 
104         for(;;)
105         {
106             int n = sc.nextInt();
107             if( n==0 ) break;
108             
109             Point points[] = new Point[n];
110             for( int i=0; i<n; i++ )
111             {
112                 int x = sc.nextInt();
113                 int y = sc.nextInt();
114                 points[i] = new Point( x, y );
115             }
116             
117             double smallest = Double.MAX_VALUE;
118             double largest = 0.0;
119             
120             for( int i=0; i<n; i++ ) for( int j=i+1; j<n; j++ ) for( int k=j+1; k<n; k++ )
121             {
122                 double area = heron( points[i], points[j], points[k] );
123                 if( area<smallest ) smallest = area;
124                 if( area>largest ) largest = area;
125             }
126             
127             System.out.printf( "%.1f %.1f", smallest, largest );
128             System.out.println();
129             ps.printf( "%.1f %.1f", smallest, largest );
130             ps.println();
131         }
132     }
133     
134     /**
135      * @param args
136      */
137     public static void main( String[] args ) throws Exception
138     {
139         long start = System.currentTimeMillis();
140         new triangles_vanb_slow().doit();       
141         System.out.println( System.currentTimeMillis() - start );
142     }   
143 }