usaco_rect1-矩形切割.cpp

usaco自己做的1到5章的代码

//基本思路，切割矩形的方法，利用两个队列轮流存储信息
/*
TASK: rect1
LANG: C++
*/
 
#include <iostream>
#include <fstream>
#include <algorithm>
#include <stdio.h>
#include <queue>
 
using namespace std;
 
ifstream fin("rect1.in");
ofstream fout("rect1.out");
 
int A,B,N;
struct rect
{
	short int x1,x2;
	short int y1,y2;
	short int color;
	bool state;
	rect(int X1,int X2,int Y1,int Y2)
	{
		x1=X1;y1=Y1;x2=X2;y2=Y2;
	}
	rect(){}
	void reset(int X1,int X2,int Y1,int Y2,int c)
	{
		x1=X1;y1=Y1;x2=X2;y2=Y2;
		color=c;
	}
 
};
 
//两个队列
queue<rect> r;
queue<rect> r2;
queue<rect> *R1,*R2;
 
int ans[6000];
 
//判断矩形a是否在矩形b中
bool InRect(rect &a,rect &b)
{
	if (a.x1>=b.x1 && a.x2<=b.x2 && a.y1>=b.y1 && a.y2<=b.y2) return true;
	return false;
}
 
//将矩形b对矩形a进行划分
void Divide(rect &a,rect &b)
{
	//如果两个矩形不相交，则直接将a压入队列
	if (a.x1>b.x2 || a.x2<b.x1) 
	{
		R2->push(a);
		return;
	}
	if (b.y2<a.y1 || a.y2<b.y1)
	{
		R2->push(a);
		return;
	}
 
	//如果b包含a，则直接跳过
	if (a.x1>=b.x1 && a.x2<=b.x2 && a.y1>=b.y1 && a.y2<=b.y2) return;
 
	//否则，截取划分坐标
	int i,j;
	int divx[4];
	int divy[4];
	int xs=0,ys=0;
	rect temp;
	temp.color=a.color;
 
	divx[xs++]=a.x1;
	if (b.x1>a.x1 && b.x1 <a.x2) divx[xs++]=b.x1;
	if (b.x2>a.x1 && b.x2 <a.x2) divx[xs++]=b.x2;
	divx[xs++]=a.x2;
 
	divy[ys++]=a.y1;
	if (b.y1>a.y1 && b.y1<a.y2) divy[ys++]=b.y1;
	if (b.y2>a.y1 && b.y2<a.y2) divy[ys++]=b.y2;
	divy[ys++]=a.y2;
 
	//划分
	for (i=0;i<xs-1;++i)
		for (j=0;j<ys-1;++j)
		{
			temp.x1=divx[i];
			temp.x2=divx[i+1];
			temp.y1=divy[j];
			temp.y2=divy[j+1];
			//如果面积为0，跳过
			if (temp.x1==temp.x2 || temp.y1==temp.y2) continue;
			//如果划分出来的矩形是b的一部分，跳过
			if (!InRect(temp,b)) R2->push(temp);
		}
 
}
 
//交换两个队列指针
void Swap(queue<rect> *&a,queue<rect> *&b)
{
	queue<rect> * temp;
	temp=a;
	a=b;
	b=temp;
}
 
void init()
{
	fin>>A>>B>>N;
 
	//初始化一个队列
	rect temp,temp2;
	temp.reset(0,A,0,B,1);
	r.push(temp);
 
	R1=&r;R2=&r2;
 
	int i,j,k;
 
	for (k=1;k<=N;++k)
	{
		//每次读入一个矩形
		fin>>temp.x1>>temp.y1>>temp.x2>>temp.y2>>temp.color;
		//如果矩阵坐标超过范围，剪掉
		if (temp.x2>=A) temp.x2=A;
		if (temp.y2>=B) temp.y2=B;
 
		//当队列R1非空
		while (!R1->empty())
		{
			//取一个元素，进行切割
			temp2=R1->front();
			R1->pop();
			Divide(temp2,temp);
		}
 
		R2->push(temp);
 
		//交换指针
		Swap(R1,R2);
 
	}
 
 
	//计算面积
	memset(ans,0,sizeof(0));
	while (!R1->empty())
	{
		temp=R1->front();
		R1->pop();
		ans[temp.color]+=(temp.x2-temp.x1)*(temp.y2-temp.y1);
	}
 
	//输出答案
	for (i=1;i<=2500;++i) if (ans[i]>0) fout<<i<<" "<<ans[i]<<endl;
 
}
 
 
int main()
{
	init();
 
	//system("pause");
	return 0;
}