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