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