USACO 3.1.4 Shaping Regions

USACO 3.1.4 Shaping Regions 形成的区域 - BYVoid

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)

1. 20 20 3  
2. 2 2 18 18 2  
3. 0 8 19 19 3  
4. 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:

1. 11111111111111111111  
2. 33333333443333333331  
3. 33333333443333333331  
4. 33333333443333333331  
5. 33333333443333333331  
6. 33333333443333333331  
7. 33333333443333333331  
8. 33333333443333333331  
9. 33333333443333333331  
10. 33333333443333333331  
11. 33333333443333333331  
12. 33333333443333333331  
13. 11222222442222222211  
14. 11222222442222222211  
15. 11222222442222222211  
16. 11222222442222222211  
17. 11222222442222222211  
18. 11222222442222222211  
19. 11111111441111111111  
20. 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. 1 91  
2. 2 84  
3. 3 187  
4. 4 38  

https://www.byvoid.com/blog/usaco-314-shaping-regions/
N个不同的颜色的不透明的长方形(1 <= N <= 1000)被放置在一张横宽为A竖长为B的白纸上。 这些长方形被放置时，保证了它们的边与白纸的边缘平行。 所有的长方形都放置在白纸内，所以我们会看到不同形状的各种颜色。 坐标系统的原点(0,0)设在这张白纸的左下角，而坐标轴则平行于边缘。

给出每个玻璃的颜色，求它们按一定的顺序叠放后垂直方向上能被看到的各种颜色的面积。

标准解法是离散化。但是处于简单易行考虑，最优解法是倒序染色+分割矩形。
http://www.cnblogs.com/ay27/archive/2012/12/08/2809324.html

什么是灌水法？就是把每一个矩形都标记一遍，最后扫描整个大矩阵，算法的时间复杂度是O(N^2)，看数据规模就知道肯定死翘翘了。

这题我选用了漂浮法，也称碰撞法。

漂浮法在nocow上是这样描述的：

漂浮法

以逆序来进行放置，即n to 1。逆序的好处在于放置一个矩形后，俯视看到的就是最终俯视该矩形应该看到的。因为挡着它的矩形在之前已经放置好了，所以可直接统计，为递归创造了条件。每放一个矩形，可以想象成将其扔入一密度很大的海水底部，海分成了n层,然后矩形开始向上浮。在上浮过程中若碰撞到其他的矩形则断裂成几个小矩形，继续上浮，直到浮出水面。于是想到用个递归来模拟上浮过程。

下面是我的个人见解：

我们先考虑简单的情况：

         情况1                               情况2                                    情况3                                   情况4

      

这是最简单的4种遮挡情况，而复杂的遮挡情况总可以通过矩阵分割得到上面几种情况，举个例子：

对于这样的遮挡，我们可以这样分割：

把这种情况看成是情况1进行处理，先处理蓝色的部分，对于右边部分进行递归，按照情况3进行处理，其他所有的遮挡情况均可类似分割。

值得注意的是以下的遮挡情况：

我们需要进行如下切割：

这个需要对切割时的判断条件进行精确的描述。

到此，我们已经找到了处理遮挡的一般方法，下面进行总结：

1.我们可以从最底部，也可以从最顶部开始处理每个矩阵，这里采用从最底部的矩阵开始处理；

2.枚举每一个矩阵，与当前处理的矩阵进行遮挡处理，这个遮挡处理的递归终止条件是分割的小矩阵已处于最顶部；

3.统计每个颜色的面积。

http://sdjl.me/index.php/archives/119
Read full article from USACO 3.1.4 Shaping Regions 形成的区域 - BYVoid