2013-12-05 16:03:32Morris

[UVA] 11601 - Avoiding Overlaps

F

Avoiding Overlaps

Input: Standard Input

Output: Standard Output

 

Given N regular rectangles in a sequence.  Following this sequence you have to draw every rectangles if it does not overlap with any rectangle which has been drawn already. Calculate the total area of drawn rectangles.

 

Note:  A rectangle is regular if and only if it’s sides are all parallel to the axis.

 

Input

The first line of the input contains the number of test cases T (1 ≤ T ≤ 100).  Each case starts with a single line containing N(0 ≤ N ≤ 10000), the number of rectangles in the sequence. Next N lines will represent the sequence of rectangles. Each of the next N lines will represent one rectangle having four integers x1, y1, x2, y2 (-100 < x1, y1, x2, y2 < 100, x1<x2, y1<y2), here (x1, y1) is the lower left corner of the rectangle and (x2, y2) is the upper right corner of the rectangle.
                                                                                                                                                         

Output

For each test case, print the case number and a single integer, the total area covered by rectangles you drew.

 

Sample Input                               Output for Sample Input

1

3

-1 -1 1 1

0 0 10 10

1 0 2 2

Case 1: 6

 

Warning: The size of input file is around 12 MB.


Problemsetter: Md. Arufuzzaman Arif

Special Thanks: Sohel Hafiz

題目描述:

每一次嘗試貼一個矩形上去,如果不會蓋到別人矩形的話便這麼做,反之則捨棄。
問最後貼了多少面積。

題目解法:

1) 使用 2D binary indexed tree

由於不管怎樣,答案一定小於 200*200,O(40000) 是可以接受的蠻幹。
為了方便查找使用
2D binary indexed tree

檢查
跟填入都是 O(lgn lgn),單筆大概是 64 次左右。
而計算區域是否有其他的矩形則會耗到 64*4 次。

#include <stdio.h>
#include <string.h>
#define maxL 205
int tree[maxL][maxL];
void modify(int x, int y) {
    int yy;
    while(x < maxL) {
        yy = y;
        while(yy < maxL) {
            tree[x][yy]++;
            yy += yy&(-yy);
        }
        x += x&(-x);
    }
}
int query(int x, int y) {
    int ret = 0, yy;
    while(x) {
        yy = y;
        while(yy) {
            ret += tree[x][yy];
            yy -= yy&(-yy);
        }
        x -= x&(-x);
    }
    return ret;
}
int isEmpty(int x1, int y1, int x2, int y2) {
    int r1, r2, r3, r4;
    r1 = query(x2, y2);
    r2 = query(x2, y1-1);
    r3 = query(x1-1, y2);
    r4 = query(x1-1, y1-1);
    r1 = r1 - r2 - r3 + r4;
    return r1 == 0;
}
int main() {
    int testcase, cases = 0;
    int n, i, j;
    int x1, y1, x2, y2;
    scanf("%d", &testcase);
    while(testcase--) {
        scanf("%d", &n);
        memset(tree, 0, sizeof(tree));
        int ret = 0;
        while(n--) {
            scanf("%d %d %d %d", &x1, &y1, &x2, &y2);
            x2--, y2--;
            x1 += 100, y1 += 100, x2 += 100, y2 += 100;
            int f = isEmpty(x1, y1, x2, y2);
            if(f == 1) {
                for(i = x1; i <= x2; i++) {
                    for(j = y1; j <= y2; j++) {
                        ret++;
                        modify(i, j);
                    }
                }
            }
        }
        printf("Case %d: %d\n", ++cases, ret);
    }
    return 0;
}

2) 使用位元壓縮

因此狀態量 200*200/64。

最慘單筆操作 625,與 1) 速度相差兩倍左右,但實際計算時並不會到最慘情況。

因此速度反而比較快。

#include <stdio.h>
#include <string.h>
typedef unsigned long long ULL;
ULL g[205][205/64+1];

int isEmpty(int x1, int y1, int x2, int y2) {
    int x, l, r;
    int yy1, yy2;
    for(x = x1; x <= x2; x++) {
        yy1 = y1, yy2 = y2;
        while((yy1&63) && yy1 <= yy2) {
            if(g[x][yy1>>6]>>(yy1&63)&1)
                return 0;
            yy1++;
        }
        while(((yy2+1)&63) && yy2 >= yy1) {
            if(g[x][yy2>>6]>>(yy2&63)&1)
                return 0;
            yy2--;
        }
        if(yy1 > yy2)    continue;
        l = yy1>>6, r = yy2>>6;
        while(l <= r) {
            if(g[x][l])
                return 0;
            l++;
        }
    }
    return 1;
}
void modify(int x, int y) {
    g[x][y>>6] |= 1LL<<(y&63);
}
int main() {
    int testcase, cases = 0;
    int n, i, j;
    int x1, y1, x2, y2;
    scanf("%d", &testcase);
    while(testcase--) {
        scanf("%d", &n);
        memset(g, 0, sizeof(g));
        int ret = 0;
        while(n--) {
            scanf("%d %d %d %d", &x1, &y1, &x2, &y2);
            x2--, y2--;
            x1 += 100, y1 += 100, x2 += 100, y2 += 100;
            int f = isEmpty(x1, y1, x2, y2);
            if(f == 1) {
                for(i = x1; i <= x2; i++) {
                    for(j = y1; j <= y2; j++) {
                        ret++;
                        modify(i, j);
                    }
                }
            }
        }
        printf("Case %d: %d\n", ++cases, ret);
    }
    return 0;
}