Shaping Regions

形成的区域
译 by tim green


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

PROGRAM NAME: rect1

INPUT FORMAT
每行输入的是放置长方形的方法。
第一行输入的是那个放在底的长方形(即白纸)。
第 1 行:       A ， B 和 N, 由空格分开 (1 <=A, B<=10,000)
第 2 到N+1行:  为五个整数　llx, lly, urx, ury, color　这是一个长方形的左下角坐标，右上角坐标和颜色。
颜色 1和底部白纸的颜色相同。

SAMPLE INPUT (file rect1.in)
20 20 3
2 2 18 18 2
0 8 19 19 3
8 0 10 19 4

OUTPUT FORMAT
输出文件应该包含一个所有能被看到颜色连同该颜色的总面积的清单( 即使颜色的区域不是连续的)，按color的增序顺序。
不要显示没有区域的颜色。

SAMPLE OUTPUT (file rect1.out)
1 91
2 84
3 187
4 38

if (m[j].lly <= y_coord[i] && y_coord[i + 1] <= m[j].ury)

最初由 RoBa 发布
学习

我写过230行的，汗。。。

我听到的说法是，大牛能够在比赛中敲出二百多行的代码，仍然面不改色，然后一次编译通过，然后一次提交就AC

/* ShapingRegions.cpp
ID: Zmworm[CCG]
PROG: rect1
LANG: C++
*/

#include "stdafx.h"
#include <map>
#include <vector>
#include <fstream>

#define MAX_SIZE  0x200
#define MAX_COORD MAX_SIZE * sizeof(int) * 8  //坐标最大值 16384

typedef struct tagMatrix
{
	int llx, lly, urx, ury, color;
} Matrix; //一个矩形结构
 
Matrix BackRect;//白纸信息
static unsigned int  Coordinate [MAX_SIZE * MAX_COORD] ;//坐标数组 要浪费32M内存-__-||
std::map<int,int> ColorInfo;  //第一项为颜色类型，第二项为该颜色的数量
std::vector<Matrix> RectInfo; //保存从文件中读取的所有矩形信息

int init();
unsigned int check(int x,int y); //非零表示这个点已经被覆盖过了

int main()
{
	if (0 == init()) //读取元素，并进行检查
		return -1;
	
	int i,j,k;
	i = (int)RectInfo.size() - 1;
	ColorInfo[1] = BackRect.urx * BackRect.ury; //开始全是白色

	for(i ;i >= 0 ;--i) //倒序读取
		for(j = RectInfo[i].llx;j < RectInfo[i].urx ; ++j) //遍历一个矩形元素的x点
			for(k = RectInfo[i].lly;k < RectInfo[i].ury ;++k) //遍历一个矩形元素的y点
				if(0 == check(j,k))
				{
					ColorInfo[RectInfo[i].color]  += 1;  //如果该点没有占用，此颜色数目加1
					ColorInfo[1] -=1;					//背景色减一，如果为0也可以跳出循环，并输出结果。
				};
	//输出结果
	std::ofstream fout("rect1.out");
	std::map<int, int>::iterator it;
	for(it = ColorInfo.begin();it != ColorInfo.end();++it)
		if( it->second != 0)
			fout << it->first << " " << it->second << "\n";
	fout.close();

	return 1;
}

int init()
{
	std::ifstream fin("rect1.in");
	if(fin.fail())
		return -1;

	int i = 0, count;
	fin >> BackRect.urx >> BackRect.ury >> count;
	if (BackRect.urx > MAX_COORD || BackRect.ury > MAX_COORD || 0 == BackRect.ury || 0 == BackRect.ury)
		return -1; //检查白纸是否合法

	Matrix eTemp;
	while(!fin.eof() && i < count)
	{
		++i;
		fin >> eTemp.llx >> eTemp.lly >> eTemp.urx >> eTemp.ury >> eTemp.color;
		if(eTemp.llx < eTemp.urx && eTemp.lly < eTemp.ury && eTemp.urx <= BackRect.urx && eTemp.ury <= BackRect.ury)
			RectInfo.push_back(eTemp);//如果矩形数据合法，则加入这条信息
	}

	fin.close();

	for (i =0;i< MAX_SIZE * MAX_COORD;++i)
		Coordinate [i] = 0;//初始化白纸数组

	return 1;
}

unsigned int check(int x,int y)
{
	int nResult;
	int i = (y * BackRect.urx +x) / 32
	int j = (y * BackRect.urx +x) % 32); //坐标转成白纸数组中的位置
	unsigned int uMark = 1;
	uMark  = uMark << j;
	nResult = Coordinate[i] & uMark; //获得结果
	Coordinate[i] |=  uMark ;//标记该点已经覆盖

	return nResult;
}

最初由 luocong 发布
呵呵，第一个case过不了。。。因为USACO规定程序最多只能用16M内存。下面是运行结果：

TASK: rect1
LANG: C++

........

┌─┬─┬─┐
│  │上│  │
│  ├─┤  │
│左│  │右│
│  ├─┤  │
│  │下│  │
└─┴─┴─┘

/* ShapingRegions2.cpp
ID: Zmworm[CCG]
PROG: rect1
LANG: C++
*/

#include "stdafx.h"
#include <fstream>

#define MAX_COORD 10000
#define MAX_N 1000
#define MAX_COLOR MAX_N + 2
#define max(a,b) (((a) > (b)) ? (a) : (b))
#define min(a,b) (((a) < (b)) ? (a) : (b))

typedef struct tagMatrix
{
	int llx, lly, urx, ury, color;
} Matrix, *pMatrix; //一个矩形结构
 
Matrix BackRect ;//白纸信息
int RectDepth;//矩形的深度，为矩形总数量减一
static unsigned int  ColorInfo[MAX_COLOR];  //序号为颜色类型，第二项为该颜色的数量
Matrix  RectInfo[MAX_N] ; //保存从文件中读取的所有矩形信息

int init();
int DivRect(int nLayer, pMatrix matrix, int size);

int main()
{
	if (0 == init()) //读取元素，并进行检查
		return 1;
	
	int i,j,k,temp;
	ColorInfo[1] = BackRect.urx * BackRect.ury; //开始全是白色

	for(i=0;i <= RectDepth;i++)//切割矩形
	{
		DivRect(i,&RectInfo[i],1);
	}

	//输出结果
	std::ofstream fout("rect1.out");
	for(i = 0;i < MAX_COLOR;++i)
		if(   ColorInfo[i] != 0)
			fout << i << " " << ColorInfo[i]<< "\n";
	fout.close();

	return 0;
}

int init()
{
	std::ifstream fin("rect1.in");
	if(fin.fail())
		return -1;

	int i = 0;
	fin >> BackRect.urx >> BackRect.ury >> RectDepth;
	if (BackRect.urx > MAX_COORD || BackRect.ury > MAX_COORD || 0 == BackRect.ury || 0 == BackRect.ury)
		return -1; //检查白纸是否合法
	RectDepth -= 1;//深度为矩形数量减一，因为深度是从0开始的

	Matrix eTemp;
	while(!fin.eof() && i <= RectDepth)
	{
		fin >> eTemp.llx >> eTemp.lly >> eTemp.urx >> eTemp.ury >> eTemp.color;
		if(eTemp.llx < eTemp.urx && eTemp.lly < eTemp.ury && eTemp.urx <= BackRect.urx && eTemp.ury <= BackRect.ury && eTemp.color < MAX_COLOR)
			RectInfo[i] =eTemp;//如果矩形数据合法，则加入这条信息
		++i;
	}
	fin.close();

	return 1;
}

int DivRect(int nLayer, pMatrix matrix, int size)
{
	int i,nAcreage;
	if( RectDepth == nLayer)
	{//如果到了最后一层，就输出结果
		for(i = 0;i<size;++i)
		{
			nAcreage = (matrix[i].urx - matrix[i].llx) * (matrix[i].ury - matrix[i].lly);
			ColorInfo[matrix->color] += nAcreage;//增加该区域颜色
			ColorInfo[1] -= nAcreage;//从白色区域中去除
		}
		return 1;
	}

	for(i = 0; i<size; ++i)
	{
		int ax =matrix[i].llx;//要切割的矩形
		int ay =matrix[i].lly;
		int bx =matrix[i].urx;
		int by =matrix[i].ury;
		int Ax =RectInfo[nLayer+1].llx;//下一层的矩形
		int Ay =RectInfo[nLayer+1].lly;
		int Bx =RectInfo[nLayer+1].urx;
		int By =RectInfo[nLayer+1].ury;

		if   (bx < Ax || ax > Bx || by <Ay || ay > By)
		{//两矩形没有相交
			DivRect(nLayer+1,matrix+i,1);
		}
		else
		{//处理两矩形相交时的情况，就是把矩形分成四部分
			pMatrix pDivRect1 = new Matrix[4];
			int j = 0;
			if (by > By)//上区
			{
				pDivRect1[j].color = matrix[0].color;
				pDivRect1[j].llx = max(ax,Ax);
				pDivRect1[j].lly = By;
				pDivRect1[j].urx = min(bx,Bx);
				pDivRect1[j].ury = by;
				++j;			
			}
			if(Ay > ay)//下区
			{
				pDivRect1[j].color = matrix[0].color;
				pDivRect1[j].llx = max(ax,Ax);
				pDivRect1[j].lly = ay;
				pDivRect1[j].urx = min(bx,Bx);
				pDivRect1[j].ury = Ay;
				++j;				
			}
			if(ax < Ax)//左区
			{
				pDivRect1[j].color = matrix[0].color;
				pDivRect1[j].llx = ax;
				pDivRect1[j].lly = ay;
				pDivRect1[j].urx = Ax;
				pDivRect1[j].ury = by;
				++j;
			}
			if(Bx < bx)//右区
			{
				pDivRect1[j].color = matrix[0].color;
				pDivRect1[j].llx = Bx;
				pDivRect1[j].lly = ay;
				pDivRect1[j].urx = bx;
				pDivRect1[j].ury = by;
				++j;
			}
			if(j)//如果切割出矩形，则进入下一层
			DivRect(nLayer+1,pDivRect1,j);

			delete pDivRect1;
		}
	}

	return 1;
}