triangles/Triangles_artur.java

  1 import java.awt.Point;
  2 import java.io.BufferedReader;
  3 import java.io.InputStreamReader;
  4 import java.util.Arrays;
  5 import java.util.Comparator;
  6 import java.util.StringTokenizer;
  7 
  8 public class Triangles_artur {
  9 
 10   static final int MAXN = 2010;
 11   static final Point[] a = new Point[MAXN];
 12   static {
 13     for (int i = 0; i < MAXN; i++)
 14       a[i] = new Point();
 15   }
 16 
 17   public static void main(String[] args) throws Exception {
 18     BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
 19 
 20     while (true) {
 21       int n = Integer.parseInt(in.readLine());
 22       if (n == 0)
 23         break;
 24 
 25       StringTokenizer str;
 26       for (int i = 0; i < n; i++) {
 27         str = new StringTokenizer(in.readLine());
 28         a[i].x = Integer.parseInt(str.nextToken());
 29         a[i].y = Integer.parseInt(str.nextToken());
 30       }
 31 
 32       int k = n * (n - 1) / 2;
 33       Event[] events = new Event[k];
 34       for (int i = 0; i < n; i++)
 35         for (int j = i + 1; j < n; j++)
 36           events[--k] = new Event(i, j);
 37       Arrays.sort(events);
 38 
 39       Integer[] ptr = new Integer[n];
 40       for (int i = 0; i < n; i++)
 41         ptr[i] = i;
 42       Arrays.sort(ptr, new Comparator<Integer>() {
 43         public int compare(Integer f, Integer g) {
 44           int dy = a[f].y - a[g].y;
 45           return dy == 0 ? (a[f].x - a[g].x) : dy;
 46         }
 47       });
 48 
 49       int[] rev = new int[n];
 50       for (int i = 0; i < n; i++)
 51         rev[ptr[i]] = i;
 52 
 53       int bestmin = Integer.MAX_VALUE, bestmax = Integer.MIN_VALUE;
 54       for (Event e : events) {
 55         k = Math.min(rev[e.i], rev[e.j]) - 1;
 56         if (k > -1) {
 57           bestmin = Math.min(twiceArea(a[e.i], a[e.j], a[ptr[k]]), bestmin);
 58           bestmax = Math.max(twiceArea(a[e.i], a[e.j], a[ptr[0]]), bestmax);
 59         }
 60 
 61         k = Math.max(rev[e.i], rev[e.j]) + 1;
 62         if (k < n) {
 63           bestmin = Math.min(twiceArea(a[e.i], a[e.j], a[ptr[k]]), bestmin);
 64           bestmax = Math.max(twiceArea(a[e.i], a[e.j], a[ptr[n - 1]]), bestmax);
 65         }
 66 
 67         k = ptr[rev[e.i]];
 68         ptr[rev[e.i]] = ptr[rev[e.j]];
 69         ptr[rev[e.j]] = k;
 70 
 71         k = rev[e.i];
 72         rev[e.i] = rev[e.j];
 73         rev[e.j] = k;
 74       }
 75 
 76       System.out.printf("%.1f %.1f\n", bestmin / 2.0, bestmax / 2.0);
 77     }
 78   }
 79 
 80   static int twiceArea(Point a, Point b, Point c) {
 81     return Math.abs((a.x - c.x) * (b.y - c.y) - (a.y - c.y) * (b.x - c.x));
 82   }
 83 
 84   static class Event implements Comparable<Event> {
 85     int i, j, dx, dy, right, left;
 86 
 87     Event(int i, int j) {
 88       this.i = i;
 89       this.j = j;
 90       dx = a[i].x - a[j].x;
 91       dy = a[i].y - a[j].y;
 92       if (dy == 0 && dx < 0)
 93         dx = -dx;
 94       else if (dy < 0) {
 95         dx = -dx;
 96         dy = -dy;
 97       }
 98       left = Math.min(a[i].x, a[j].x);
 99       right = Math.max(a[i].x, a[j].x);
100     }
101 
102     public int compareTo(Event that) {
103       int temp = this.dy * that.dx - this.dx * that.dy;
104       if (temp == 0)
105         temp = this.left - that.left;
106       if (temp == 0)
107         temp = this.right - that.right;
108       return temp;
109     }
110   }
111 }