时间过得好快，距离上一次写解题报告也仅仅过去了两个多月了。贵在加持。Hope the waiting will have a sweet end. God bless me.
此题由于后面讲到的难点，卡了很久，代码越写越恶心后，看到http://belbesy.wordpress.com/2012/08/13/usaco-3-1-3-shaping-regions/这里茅塞顿开。可以直接移步上述链接。
这个题的大意是有许多方块，后放置的方块会覆盖之前的方块的颜色，让统计最后显示出来的颜色所占据的面积。
题目的提示里面已经指出，按照方块保存颜色信息，即左下角和右上角的坐标，以及颜色，而不是按照题目的描述，每次都暴力染色。这样时间和空间消耗都会大大减少。
之前很少接触设计几何图形的题，所以难点主要集中在两点：
1.如何判断两个矩形是否有重叠(intersect)。
判断Square square(ll, lr, ul, ur, color)和squares[j]是否重叠代码如下：
int maxll, maxlr, minul, minur;
maxll = max(ll, squares[j].ll);
maxlr = max(lr, squares[j].lr);
minul = min(ul, squares[j].ul);
minur = min(ur, squares[j].ur);
if(maxll >= minul || maxlr >= minur)//没有重叠
{
continue;
}
对比图1:
我们可以知道，如果A点完全在B点的右侧或上侧，则两个矩形没有重叠。
2.如何将重叠产生的图形划分为矩形的形式。这里需要找到一种通用的表达方法，别的相交的情况（比如重叠了四个角中的任一个或两个角）都能成为其特殊情况。
代码如下：
addSquare(squares, Square(squares[j].ll, squares[j].lr, maxll, squares[j].ur, squares[j].color)); addSquare(squares, Square(maxll, minur, minul, squares[j].ur, squares[j].color)); addSquare(squares, Square(minul, squares[j].lr, squares[j].ul, squares[j].ur, squares[j].color)); addSquare(squares, Square(maxll, squares[j].lr, minul, maxlr, squares[j].color));
addSquare方法第二个参数为新加入的矩形（由被覆盖的矩形中没被覆盖的部分分割而成），共有四个，分别对应图2中的（1），（2），（3），（4）。当然，原来的两个矩形，被覆盖的矩形需要标记为不可用（我采用的方法）或删除，另一个矩形完整加入。
这就是通用的情况，别的相交的情况都是上图的特例。比如图1中只包含(1)和(4)，剩下的(2)和(3)退化为一条线。因此，所有的相交后的矩形都可以这么处理，加入的时候需要判断下是否变形（面积大于0）。
完整代码如下：
/*
ID: thestor1
LANG: C++
TASK: rect1
*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <cassert>
#include <list>
#include <map>
using namespace std;
struct Square{
int ll, lr, ul, ur;
int color;
int area;
bool cut;
Square()
{
}
Square(int ll, int lr, int ul, int ur, int color)
{
this->ll = ll;
this->lr = lr;
this->ul = ul;
this->ur = ur;
this->color = color;
this->area = (ul - ll) * (ur - lr);
this->cut = false;
}
};
void addSquare(vector<Square> &squares, const Square& square)
{
if(square.area != 0)
{
squares.push_back(square);
}
}
int main()
{
FILE *fin = fopen ("rect1.in", "r");
FILE *fout = fopen ("rect1.out", "w");
//freopen("log.txt", "w", stdout);
int a, b, n;
fscanf(fin, "%d%d%d", &a, &b, &n);
vector<Square> squares;
squares.push_back(Square(0, 0, a, b, 1));
for(int i = 0; i < n; ++i)
{
int ll, lr, ul, ur, color;
fscanf(fin, "%d%d%d%d%d", &ll, &lr, &ul, &ur, &color);
Square square(ll, lr, ul, ur, color);
for(unsigned int j = 0; j < squares.size(); ++j)
{
if(!squares[j].cut)
{
int maxll, maxlr, minul, minur;
maxll = max(ll, squares[j].ll);
maxlr = max(lr, squares[j].lr);
minul = min(ul, squares[j].ul);
minur = min(ur, squares[j].ur);
if(maxll >= minul || maxlr >= minur)
{
continue;
}
squares[j].cut = true;
addSquare(squares, Square(squares[j].ll, squares[j].lr, maxll,
squares[j].ur, squares[j].color));
addSquare(squares, Square(maxll, minur, minul,
squares[j].ur, squares[j].color));
addSquare(squares, Square(minul, squares[j].lr, squares[j].ul,
squares[j].ur, squares[j].color));
addSquare(squares, Square(maxll, squares[j].lr, minul,
maxlr, squares[j].color));
}
}
addSquare(squares, square);
}
map<int, int> cntColors;
for(unsigned int i = 0; i < squares.size(); ++i)
{
if(!squares[i].cut)
{
if(cntColors.find(squares[i].color) == cntColors.end())
{
cntColors[squares[i].color] = squares[i].area;
}
else
{
cntColors[squares[i].color] += squares[i].area;
}
}
}
for(map<int, int>::iterator iter = cntColors.begin(); iter != cntColors.end(); ++iter)
{
fprintf(fout, "%d %d\n", iter->first, iter->second);
}
return 0;
}