Sicily 1913. Slides

1913. Slides

Constraints

Time Limit: 1 secs, Memory Limit: 32 MB

Description

 There are N slides lying on the table. Each of them is transparent and formed as a rectangle. In a traditional problem, one may have to calculate the intersecting area of these N slides. The definition of intersection area is such area which belongs to all of the slides.

But this time I want to take out some one of the N slides, so that the intersecting area of the left N - 1 slides should be maximal. Tell me the maximum answer.

Input

 The first line of the input contains a single integer T , the number of test cases, followed by the input data for each test case. The first line of each test case contains a single integer N (1 ≤ N ≤ 100) , the number of rectangles. Followed by N lines, each line contains four integers x1 , y1 , x2 , y2 (- 10000 ≤ x1 < x2 ≤ 10000, -10000 ≤ y1 < y2 ≤ 10000) , pair (x1, y1) gives out the bottom-left corner and pair (x2, y2) gives out the top-right corner of the rectangle.

Output

 There should be one line per test case containing the maximum intersecting area of corresponding N - 1 slides.

Sample Input

2 
2 
0 0 2 2 
1 1 2 2 
3 
0 0 2 2 
1 0 3 2 
1 1 3 3

Sample Output

4 
2
// Problem#: 1913
// Submission#: 3591128
// The source code is licensed under Creative Commons Attribution-NonCommercial-ShareAlike 3.0 Unported License
// URI: http://creativecommons.org/licenses/by-nc-sa/3.0/
// All Copyright reserved by Informatic Lab of Sun Yat-sen University
#include <stdio.h>
#include <algorithm>
using namespace std;

const int INF = 0x7fffffff;
const int MAXN = 100;

int x1[MAXN], y1[MAXN], x2[MAXN], y2[MAXN];

void insert_min(int a[2], int x) {
    if (x < a[0]) swap(x, a[0]);
    if (x < a[1]) swap(x, a[1]);
}

void insert_max(int a[2], int x) {
    if (x > a[0]) swap(x, a[0]);
    if (x > a[1]) swap(x, a[1]);
}

int exclude(int a[2], int x) {
    if (a[0] != x) return a[0];
    return a[1];
}

int main() {
    int cs;
    scanf("%d", &cs);
    while (cs--) {
        int left[2] = {-INF, -INF};
        int right[2] = {INF, INF};
        int bottom[2] = {-INF, -INF};
        int top[2] = {INF, INF};
        int n; 
        scanf("%d", &n);
        for (int i = 0; i < n; i++) {
            scanf("%d%d%d%d", x1 + i, y1 + i, x2 + i, y2 + i);
            insert_max(left, x1[i]);
            insert_min(right, x2[i]);
            insert_max(bottom, y1[i]);
            insert_min(top, y2[i]);
        }
        if (n == 1) {
            printf("0\n");
        } else {
            int ret = 0;
            for (int i = 0; i < n; i++) {
                int dx = exclude(right, x2[i]) - exclude(left, x1[i]);
                if (dx < 0) dx = 0;
                int dy = exclude(top, y2[i]) - exclude(bottom, y1[i]);
                if (dy < 0) dy = 0;
                ret = max(ret, dx * dy);
            }
            printf("%d\n", ret);
        }
    }
    return 0;
}