USACO 3.1.4 Shaping Regions
Shaping Regions
N opaque rectangles (1 <= N <= 1000) of various colors are placed on a white sheet of 易做图 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 易做图).
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
/*-----------------------------------------------------------------------------------------------------------*/
一开始我的想法就是开二维数组，读入一个新矩形就更新一次。但是10000*10000的数组太大了，编译都通不过。
第二个想法是根据下面的hint，把矩形分开。我想的是读入一个矩形后就去与之前读入的矩形看看，是否有重合，有的话就易做图新矩形。但是这样做的话就必须要开数组跟踪每个矩形的数据，因为矩形是在不断变化的，这样写太麻烦了。
所以只能求助于nocow，发现可以把上一个想法倒过来。从后向前，因为后面的矩形就是我们看到的。前面的矩形在不断与后面的矩形发生碰撞时不断易做图，直到最后得到的就是我们看到的矩形。而在这个过程中，后面的矩形是不会发生变化的。这种方法叫漂浮法。
我们使用递归实现。
程序：
[cpp]
/*
ID:zhaorui3
PROG:rect1
LANG:C++
*/
# include <fstream>
using namespace std;
int min(int a , int b)
{
return (a < b ? a : b);
}
int max(int a , int b)
{
return (a > b ? a : b);
}
int x1[1001] , y1[1001] , x2[1001] , y2[1001] , color[1001] = {1};
int cnt[2501] , N;
void cover(int lx , int ly , int rx , int ry , int c , int h)
{
if(lx == rx || ly == ry)
return; // 面积为0时跳出
if(h > N)
cnt[c] += (ry-ly)*(rx-lx);
else
{
if(ly < y1[h])
cover(min(lx , x2[h]) , ly , min(rx , x2[h]) , min(y1[h] , ry) , c , h+1);
if(rx > x2[h])
cover(max(x2[h] , lx) , min(y2[h] , ly) , rx , min(y2[h] , ry) , c , h+1);
if(ry > y2[h])
cover(max(x1[h] , lx) , max(y2[h] , ly) , max(rx , x1[h]) , ry , c , h+1);
if(lx < x1[h])
cover(lx , max(y1[h] , ly) , min(rx , x1[h]) , max(y1[h] , ry) , c , h+1);
}
}
int main()
{
ifstream fin("rect1.in");
ofstream fout("rect1.out");
fin >> x2[0] >> y2[0] >> N;
for (int i = 1; i <= N; ++i)
fin >> x1[i] >> y1[i] >> x2[i] >> y2[i] >> color[i];
cnt[color[N]] += (x2[N] - x1[N]) * (y2[N] - y1[N]);
for(int i = N-1 ; i >= 0 ; i--)
cover(x1[i] , y1[i] , x2[i] , y2[i] , color[i] , i+1);
for(int i = 1 ; i <= 2500 ; i++ )
if(cnt[i])
fout << i << ' ' << cnt[i] << endl;
return 0;
}
需要注意的是，如果我们易做图矩形分的不好，有可能会造成重复。矩形二在矩形一的左下方有重复，如果按照两条交线分的话，那么交线中间的部分就重复了。因此我们要事先确定分法。这里，我们约定按照下图来划分分割界线
当下面的矩形的上边界高于上面的矩形时，我们用1的分法。这个时候下面的矩形如果有2这部分的话，把它交给右边界大于上面的情况来处理。以此来避免重复。
补充：软件开发 , C++ ,
