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 /*-----------------------------------------------------------------------------------------------------------*/ 一開始我的想法就是開二維數組，讀入一個新矩形就更新一次。但是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這部分的話，把它交給右邊界大於上面的情況來處理。以此來避免重復。
