triangles/triangles_vanb.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
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.solution" ) );
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 Arrays.sort( points );
117 for( int i=0; i<n; i++ )
118 {
119 points[i].index = i;
120 }
121
122 Line lines[] = new Line[n*(n-1)/2];
123 int k=0;
124 for( int i=0; i<n; i++ ) for( int j=i+1; j<n; j++ )
125 {
126 lines[k++] = new Line( points[i], points[j] );
127 }
128 Arrays.sort( lines );
129
130 double smallest = Double.MAX_VALUE;
131 double largest = 0.0;
132 for( int i=0; i<lines.length; i++ )
133 {
134 Line line = lines[i];
135 double area;
136
137 if( !line.contains( points[n-1] ) )
138 {
139 area = heron( line.p1, line.p2, points[n-1] );
140 if( area>largest ) largest = area;
141 }
142
143 if( !line.contains( points[0] ) )
144 {
145 area = heron( line.p1, line.p2, points[0] );
146 if( area>largest ) largest = area;
147 }
148
149 int index1 = line.p1.index;
150 int index2 = line.p2.index;
151 if( index1>0 && !line.contains(points[index1-1]) )
152 {
153 area = heron( line.p1, line.p2, points[index1-1] );
154 if( area<smallest ) smallest = area;
155 }
156 if( index1<n-1 && !line.contains(points[index1+1]) )
157 {
158 area = heron( line.p1, line.p2, points[index1+1] );
159 if( area<smallest ) smallest = area;
160 }
161 if( index2>0 && !line.contains(points[index2-1]) )
162 {
163 area = heron( line.p1, line.p2, points[index2-1] );
164 if( area<smallest ) smallest = area;
165 }
166 if( index2<n-1 && !line.contains(points[index2+1]) )
167 {
168 area = heron( line.p1, line.p2, points[index2+1] );
169 if( area<smallest ) smallest = area;
170 }
171
172 points[index1] = line.p2;
173 line.p2.index = index1;
174 points[index2] = line.p1;
175 line.p1.index = index2;
176 }
177
178 ps.printf( "%.1f %.1f", smallest, largest );
179 ps.println();
180 }
181 }
182
183
184
185
186 public static void main( String[] args ) throws Exception
187 {
188 new triangles_vanb().doit();
189 }
190 }