triangles/triangles_vanb_slow.java
1
2 import java.io.*;
3 import java.util.*;
4 import java.awt.geom.*;
5
6
7
8
9
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
97
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
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 }