2013-12-05 16:03:32| 人氣2,757| 回應0 | 上一篇 | 下一篇

[UVA] 11601 - Avoiding Overlaps

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 -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;
}

我要檢舉

#11601#Avoiding Overlaps#2D binary indexed tree#位元壓縮

台長： Morris

您可能對以下文章有興趣

[UVA][模擬、旋轉] 141 - The Spot Game

[UVA][匈牙利匹配] 670 - The dog task

d094. 478 Points in Figures Rectangles ...

[UVA][dp][最優二叉樹] 12057 - Prefix Codes

人氣(2,757) | 回應(0)| 推薦 (0)| 收藏 (0)| 轉寄
全站分類: 教育學習(進修、留學、學術研究、教育概況) | 個人分類: UVA |
此分類下一篇:[UVA][匈牙利] 1514 - Piece it together
此分類上一篇:[UVA][KMP] 12604 - Caesar Cipher

回應(0)