1 /* Bulletin Board, MCPC 2008 Problem E by Andy Harrington
 2 Idea:  If all the coordinates used on each axis are listed in order, 
 3 the rectangles between two successive coordinates in each list partition the
 4 bulletin board space, and each little rectangle is either entirely under a 
 5 poster or does not overlap at all.
 6 
 7 Only a simple nested loop is needed to count how many posters cover each such
 8 atomic rectangle.  O(n^3) running time.
 9 */
10 
11 import java.util.*;
12 import java.io.*;
13 
14 public class bulletin
15 {
16     public static void main(String[] args) throws Exception {
17         String file = (args.length > 0) ? args[0] : "bulletin.in";
18         Scanner in = new Scanner(new File(file));
19         int n  = in.nextInt();
20         while (n  > 0) {
21             int[] x = new int[2*n+2]; // for all x coordinates used, including edges
22             int[] y = new int[2*n+2]; // for all y coordinates used, including edges
23             x[2*n+1] = in.nextInt();  // include largest coordinates used
24             y[2*n+1] = in.nextInt();
25             x[2*n] = y[2*n] = 0; // lowest coordinate - will sort later
26             int[] xl = new int[n]; // poster coordinates
27             int[] yl = new int[n];
28             int[] xh = new int[n];
29             int[] yh = new int[n];
30             for (int i = 0; i < n; i++) {// save each rect and all coord.
31                 x[i] = xl[i] = in.nextInt();
32                 y[i] = yl[i] = in.nextInt();
33                 x[i+n] = xh[i] = in.nextInt();
34                 y[i+n] = yh[i] = in.nextInt();
35             }
36             int nx = uniqueSeq(x); // get sorted sequences of unique elements
37             int ny = uniqueSeq(y);
38             int clearArea = 0;
39             int maxDepth = 0;
40             int maxDepthArea = 0;
41             for (int i = 1; i < nx; i++) // check each atomic rectangle
42                 for (int j = 1; j < ny; j++) {
43                     int depth = 0;
44                     for (int k = 0; k < n; k++) // check each poster
45                         if (xl[k] <= x[i-1] && x[i] <= xh[k]  &&
46                               yl[k] <= y[j-1] && y[j] <= yh[k]) 
47                             depth++;
48                     int area = (x[i] - x[i-1])*(y[j] - y[j-1]);
49                     if (depth == 0)
50                         clearArea += area;
51                     else if ( depth == maxDepth)
52                         maxDepthArea += area;
53                     else if (depth > maxDepth) {
54                         maxDepthArea = area;
55                         maxDepth = depth;
56                     }
57                 }
58             System.out.format("%d %d %d%n", clearArea, maxDepth, maxDepthArea);
59             n = in.nextInt();
60         }
61     }
62 
63     // put all the unique elements of an array in order at the front
64     // and return the count of unique numbers.
65     static int uniqueSeq(int[] a) {
66         Arrays.sort(a);
67         int inSeq = 0;  // smallest already in place
68         for (int next = 1; next < a.length; next++) 
69             if (a[inSeq] != a[next]) {
70                 inSeq++;
71                 a[inSeq] = a[next];
72             }
73         return inSeq+1;
74     }
75 }