Shaping Regions
N opaque rectangles (1 <= N <= 1000) of various colors are
placed on a white sheet of paper whose size is A wide by B long. The
rectangles are put with their sides parallel to the sheet's borders.
All rectangles fall within the borders of the sheet so that different
figures of different colors will be seen.
The coordinate system has its origin (0,0) at the sheet's lower left
corner with axes parallel to the sheet's borders.
PROGRAM NAME: rect1
INPUT FORMAT
The order of the input lines dictates the order of laying down
the rectangles. The first input line is a rectangle "on the bottom".
| Line 1: |
A, B, and N, space separated (1 <= A,B
<= 10,000) |
| Lines 2-N+1: |
Five integers: llx, lly, urx, ury,
color: the lower left coordinates and upper right coordinates of the
rectangle whose color is `color' (1 <= color <= 2500) to be placed
on the white sheet. The color 1 is the same color of white as the sheet
upon which the rectangles are placed. |
SAMPLE INPUT (file rect1.in)
20 20 3
2 2 18 18 2
0 8 19 19 3
8 0 10 19 4
INPUT EXPLANATION
Note that the rectangle delineated by 0,0 and 2,2 is two units
wide and two high. Here's a schematic diagram of the input:
11111111111111111111
33333333443333333331
33333333443333333331
33333333443333333331
33333333443333333331
33333333443333333331
33333333443333333331
33333333443333333331
33333333443333333331
33333333443333333331
33333333443333333331
33333333443333333331
11222222442222222211
11222222442222222211
11222222442222222211
11222222442222222211
11222222442222222211
11222222442222222211
11111111441111111111
11111111441111111111
The '4's at 8,0 to 10,19 are only two wide, not three (i.e., the
grid contains a 4 and 8,0 and a 4 and 8,1 but NOT a 4 and 8,2 since
this diagram can't capture what would be shown on graph paper).
OUTPUT FORMAT
The output file should contain a list of all the colors that can be seen
along with the total area of each color that can be seen (even if the
regions of color are disjoint), ordered by increasing color. Do not
display colors with no area.
SAMPLE OUTPUT (file rect1.out)
1 91
2 84
3 187
4 38
題意：
給出每個玻璃的顏色，求它們按一定的順序疊放后垂直方向上能被看到的各種顏色的面積。
代碼：
1.矩形切割
/*
LANG: C
TASK: rect1
*/
#include<stdio.h>
#define nmax 1001
struct N
{
int x1, y1, x2, y2, color;
}N[nmax];
int square[2501], currentColor, total;
void Calculation(int x1, int y1, int x2, int y2, int index)
{
do//檢查當前矩形是否沒被其他矩形覆蓋
{
index++;
}while (index <= total && (x1 >= N[index].x2 || x2 <= N[index].x1 || y1 >= N[index].y2 || y2 <= N[index].y1));
if (index > total)//如果沒被其他矩形覆蓋，則計算當前矩形面積，加到屬于顏色為currentColor的集合
{
square[currentColor] += (x2 - x1) * (y2 - y1);
}
else//如果被覆蓋，就將矩形切出沒被N[index]覆蓋的小矩形
{
if (x1 < N[index].x1)
{
Calculation(x1, y1, N[index].x1, y2, index);
x1 = N[index].x1;
}
if (x2 > N[index].x2)
{
Calculation(N[index].x2, y1, x2, y2, index);
x2 = N[index].x2;
}
if (y1 < N[index].y1)
{
Calculation(x1, y1, x2, N[index].y1, index);
y1 = N[index].y1;
}
if (y2 > N[index].y2)
{
Calculation(x1, N[index].y2, x2, y2, index);
y2 = N[index].y2;
}
}
}
int main()
{
freopen("rect1.in", "r", stdin);
freopen("rect1.out", "w", stdout);
int i, pre, width, length;
scanf("%d%d%d", &width, &length, &total);
N[0].x1 = N[0].y1 = 0, N[0].x2 = width, N[0].y2 = length, N[0].color = 1;
pre = 0;
for (i = 1; i <= total; i++)
{
scanf("%d%d%d%d%d", &N[i].x1, &N[i].y1, &N[i].x2, &N[i].y2, &N[i].color);
if (pre < N[i].color)
{
pre = N[i].color;
}
}
for (i = 0; i <= total; i++)
{
currentColor = N[i].color;
Calculation(N[i].x1, N[i].y1, N[i].x2, N[i].y2, i);
}
for (i = 1; i <= pre; i++)
{
if (square[i] > 0)
{
printf("%d %d\n", i, square[i]);
}
}
fclose(stdin);
fclose(stdout);
//system("pause");
return 0;
}
2.線段樹
/*
LANG: C
TASK: rect1
*/
#include<stdio.h>
#define nmax 15000
int cmp(const void * a, const void * b)
{
return *((int*)a) - *((int*)b);
}
int Cal[2501], ans[2501], X[2000];
struct Rec
{
int x1, y1, x2, y2, color;
}Rec[1000];
struct seg
{
int left, right, color;
}seg[3 * nmax];
void makeSeg(int left, int right, int num)
{
seg[num].left = left, seg[num].right = right, seg[num].color = 0;//顏色初始化為0
if (left + 1 == right)
{
return;
}
int mid = (left + right) >> 1;
makeSeg(left, mid, num << 1), makeSeg(mid, right, (num << 1) + 1);
}
void insert(int left, int right, int num, int color)
{
if (seg[num].left + 1 != seg[num].right)
{
if (seg[num].color)//這里讓孩子繼承父節點的color。因為插進來的線段可能覆蓋已存在的線段。
{
seg[num << 1].color = seg[(num << 1) + 1].color = seg[num].color, seg[num].color = 0;
}
}
if (left <= seg[num].left && seg[num].right <= right)//其區間在插入的線段內，設置color，表示插入該線段
{
seg[num].color = color;
return;
}
int mid = (seg[num].left + seg[num].right) >> 1;
if (right <= mid)
{
insert(left, right, num << 1, color);
}
else if (left >= mid)
{
insert(left, right, (num << 1) + 1, color);
}
else
{
insert(left, mid, num << 1, color), insert(mid, right, (num << 1) + 1, color);
}
}
void find(int num)
{
if (seg[num].color)//如果該區間存在線段，則計算給區間長度，儲存于改線段的顏色表中
{
Cal[seg[num].color] += (seg[num].right - seg[num].left);
return;
}
if (seg[num].left + 1 != seg[num].right)
{
find(num << 1), find((num << 1) + 1);
}
}
int main()
{
freopen("rect1.in", "r", stdin), freopen("rect1.out", "w", stdout);
int width, length, number, i, j, large = 0, len;
scanf("%d%d%d", &width, &length, &number);
for (i = 0, j = 0; i < number; i++)
{
scanf("%d%d%d%d%d", &Rec[i].x1, &Rec[i].y1, &Rec[i].x2, &Rec[i].y2, &Rec[i].color);
X[j++] = Rec[i].x1, X[j++] = Rec[i].x2;//儲存x軸上的點
if (large < Rec[i].y2)
{
large = Rec[i].y2;
}
}
qsort(X, j, sizeof(int), cmp);//對x軸上的點排序
len = j;
for (i = 0; i < len - 1; i++)
{
if (X[i] != X[i+1])//計算X[i]到X[i+1]上各種顏色的面積
{
makeSeg(0, large, 1);
for (j = 0; j < number; j++)
{
if (Rec[j].x1 <= X[i] && Rec[j].x2 >= X[i+1])
{
insert(Rec[j].y1, Rec[j].y2, 1, Rec[j].color);
}
}
find(1);
for (j = 2; j <= 2500; j++)
{
ans[j] += Cal[j] * (X[i+1] - X[i]);//Cal[j]是區間在X[i]到X[i+1]上顏色為j的矩形在y軸上的長度
Cal[j] = 0;
}
}
}
ans[1] = width * length;
for (i = 2; i <= 2500; i++)
{
ans[1] -= ans[i];
}
for (i = 1; i <= 2500; i++)
{
if (ans[i])
{
printf("%d %d\n", i, ans[i]);
}
}
fclose(stdin),fclose(stdout);
//system("pause");
return 0;
}