// Solution to "square count" by Bob Roos // // Solution just uses formulas I came up with for number of squares // contained within a rectangular room and number of squares that // overlap a pair of rooms. import java.util.*; import java.io.*; public class BSquareCount { public static BufferedReader in; public static StringTokenizer tok; public static int n; public static int[] x1,y1,x2,y2; public static int count; public static int caseNum; public static void main(String[] args) throws IOException { in = new BufferedReader(new InputStreamReader(System.in)); String line; caseNum = 0; while (!(line = in.readLine().trim()).equals("0")) { n = Integer.parseInt(line); caseNum++; x1 = new int[n]; y1 = new int[n]; x2 = new int[n]; y2 = new int[n]; for (int i = 0; i < n; i++) { line = in.readLine().trim(); tok = new StringTokenizer(line); x1[i] = Integer.parseInt(tok.nextToken()); y1[i] = Integer.parseInt(tok.nextToken()); x2[i] = Integer.parseInt(tok.nextToken()); y2[i] = Integer.parseInt(tok.nextToken()); // make (x1,y1) the lower left corner: if (x1[i] > x2[i]) { int temp = x1[i]; x1[i] = x2[i]; x2[i] = temp; temp = y1[i]; y1[i] = y2[i]; y2[i] = temp; } if (y1[i] > y2[i]) { int temp = y1[i]; y1[i] = y2[i]; y2[i] = temp; } } System.out.println("Case " + caseNum + ": " + sqCount()); } } public static int sqCount() { count = 0; // first, count only squares limited to a single room: for (int i = 0; i < n; i++) { int width = x2[i]-x1[i]; int height = y2[i]-y1[i]; // formula assumes width >= height, so... if (width < height) { int temp = width; width = height; height = temp; } // Following kludge prevents overflow when height and width are // large: //ORIGINAL: int k = height*(height+1)*(2*height+1)/6; int k = 1; if (height % 2 == 0) k *= (height/2) * (height+1); else k *= (height+1)/2 * height; if (k % 3 == 0) { k /= 3; k *= (2*height+1); } else k *= (2*height+1)/3; // ORIGINAL: k += (width-height)*(height)*(height+1)/2; if (height%2 == 0) k+= (height/2)*(width-height)*(height+1); else k+= ((height+1)/2)*(width-height)*height; count += k; // System.out.println("DEBUG: room["+i+"] has " + k + " squares"); } // Now for pairs of rooms. Since n <= 1000, // I'll just check all pairs of rooms for shared opening. for (int i = 0; i < n-1; i++) { for (int j = i+1; j < n; j++) { // First look at horizontal walls: int lower = i, upper = j; if (y1[i] == y2[j]) { lower = j; upper = i; } int xmin,xmax; if (y2[lower] == y1[upper]) { // Find overlap, if any: xmin = Math.max(x1[lower],x1[upper]); xmax = Math.min(x2[lower],x2[upper]); int m = xmax - xmin - 2; for (int k = 2; k <= m; k++) { if (k > y2[upper] - y1[lower]) break; // System.out.println("DEBUG: Rooms " + i + ", "+j+": "+ // ((m-k+1) * Math.min(Math.min(y2[upper]-y1[upper],y2[lower]-y1[lower]),k-1)) // +" "+k+"x"+k+" squares"); count += (m-k+1) * Math.min(Math.min(Math.min(y2[upper]-y1[upper], y2[lower]-y1[lower]),k-1),y2[upper]-y1[lower]-k+1); } } // Vertical walls: int left = i, right = j; if (x1[i] == x2[j]) { left = j; right = i; } int ymin,ymax; if (x2[left] == x1[right]) { // Find overlap, if any: ymin = Math.max(y1[left],y1[right]); ymax = Math.min(y2[left],y2[right]); int m = ymax - ymin - 2; for (int k = 2; k <= m; k++) { if (k > x2[right] - x1[left]) break; // System.out.println("Rooms " + i + ", "+j+": "+ // ((m-k+1) * Math.min(Math.min(x2[right]-x1[right],x2[left]-x1[left]),k-1)) // +" "+k+"x"+k+" squares"); count += (m-k+1) * Math.min(Math.min(Math.min(x2[right]-x1[right], x2[left]-x1[left]),k-1),x2[right] - x1[left]-k+1); } } } } return count; } }