Morris' Blog

2012-09-29 20:31:22Morris

[UVA][幾何] 11345 - Rectangles

留言 0 收藏 0 推薦 0

F - Rectangles

Time Limit: 1 sec
Memory Limit: 16MB

This problem has no story. You just have to find the common area of all rectangles.

INPUT:

The first line contains integer N (1 <= N <= 1000). It is the number of tests. Each test described by number of rectangles M (1 <= M <= 30). Next N lines contain 4 integers: X1 Y1 X2 Y2 (-10000 <= X1; Y2; X2; Y2 <= 10000). Each rectangle is described by 2 points: lower left and upper right corners. All rectangle sides are parallel to Ox or Oy axes.

OUTPUT:

For each test case out line formatter like this: "Case i: a". Where "i" is a test number, and "a" is an area that belongs to all rectangles.

SAMPLE INPUT:

1
4
0 0 10 10
-1 -1 2 2
-10 0 2 100
-10 -10 10 10

SAMPLE OUTPUT:

Case 1: 4

給的時候就是給定左下, 右上, 如果顛倒, 直接輸出 0,
特別記住 n = 1 的時候, 應該很多人會卡死這種測資


#include <stdio.h>
#define min(x, y) ((x) < (y) ? (x) : (y))
#define max(x, y) ((x) > (y) ? (x) : (y))
typedef struct {
    int x, y;
} Pt;
int main() {
    int t, cases = 0, n;
    scanf("%d", &t);
    while(t--) {
        scanf("%d", &n);
        Pt a, b, c, d;
        int i, j, k, l, tmp;
        n--;
        scanf("%d %d %d %d", &a.x, &a.y, &b.x, &b.y);
        i = a.x, j = a.y, k = b.x, l = b.y;
        int flag = 0;
        while(n--) {
            scanf("%d %d %d %d", &c.x, &c.y, &d.x, &d.y);
            i = max(a.x, c.x), j = max(a.y, c.y);
            k = min(b.x, d.x), l = min(b.y, d.y);
            if(i >= k || j >= l) {
                flag = -1;
            } else {
                a.x = i, a.y = j, b.x = k, b.y = l;
            }
        }
        if(i >= k || j >= l)    flag = -1;
        printf("Case %d: ", ++cases);
        if(!flag)   printf("%d\n", (i-k)*(j-l));
        else    printf("0\n");
    }
    return 0;
}