线段染色,矩形切割，离散化---zoj_2301,zoj_1128

         染色问题：在一维坐标轴上（最右端为M），有N个(a,b,c)的染色操作，即把在坐标(a,b)之间的线段染成颜色c.最后来求解一系列问题。如：最长的颜色为C的区间，每种颜色的总长度，每种颜色的区间段数等等。

         矩形切割问题：在二维坐标轴上，给出N个矩形，这N个矩形可能相互包含，交叉，分离。最后求解一系列问题。如N个矩形所覆盖的面积，相交的面积等。

        先来看染色问题,如果考虑坐标轴的长度为10^9数量级，而染色的操作数为1^3。那么这类问题往往需要先将连续的长度为M的区间离散化为P个染色区间.P往往是N级的。这样就将计算量大大缩短。

       如题zoj_2301,M=2^31-1,N<2000,[1 4][8 11] [3 5]这3个区间的表达方式不是端点类型（[1 4]表达的是从第一个到第四个），所以需要转化为[0 4][7 11][2 5]（[0 4]表达的是在坐标0和4之间）。

       有了上述的初始话，接下来就可以是离散化了,读取区间的所有端点，去除重复，再排序，得到一个序列{0,2,4,5,7,11}(可以用set方便实现).最后，对序列中每相邻的两个节点构造对于的区间，最后得到[0,2][2,4][4,5][5,7][7,11]这5个区间，之后的计算由此就可以大量简化。如果离散化之后的区间数为E，那么之后操作的复杂度为E*N，如果再使用线段树，可以优化为log(e)*N.

      再来看矩形切割问题,如果考虑到坐标所取的范围为M,10^9数量级，而给出的的矩形数为N=10^2.那么考虑延长每个矩形的每一条边，最后可以将坐标平面的分割成一个网格，而网格的数量级为N*N=10^4远小于10^9，由此可以简化计算。同样，再使用一维线段树可以将问题简化为NlogN,使用二维线段树可以简化为logNlogN具体见zoj_1128
    zoj_2301

 

#include<iostream>
#include<cstdio>
#include<set>
#include<vector>
using namespace std;
class line
{
public:
	int left;
	int right;
	char c;
	line(int left,int right,char c)
	{
		this->left=left;
		this->right=right;
		this->c=c;
	}	
};
int l,r,n,size;
char c;
set<int>map;
vector<line>v;
bool check(int l,int r)
{
	char c='b';
	for(int i=0;i<size;i++)
	{
		if(l>=v[i].left&&r<=v[i].right)
		c=v[i].c;
	}
	if(c=='w')	
	return true;
	else
	return false;
}
int main()
{
	freopen("e:\\zoj\\zoj_2301.txt","r",stdin);
	while(scanf("%d",&n)!=EOF)
	{
	map.clear();
	while(n--)
	{
		scanf("%d %d %c",&l,&r,&c);	
		v.push_back(line(l-1,r,c));
		map.insert(l-1);
		map.insert(r);
		size=v.size();	
	}
		int max=-1;
		int mid=0;
		bool con=false;
		int east=-1;
		for(set<int>::iterator it=map.begin();it!=map.end();it++)
		{
			int left=*it;
			it++;
			if(it==map.end())
			{
				it--;
				break;
			}
			int right=*it;
			it--;	
			if(check(left,right))
			{
				con=true;
				mid+=(right-left);
				if(mid>max)
				{
					max=mid;
					east=right;
				}	
			}
			else
			{
				con=false;
				mid=0;
			}			
		}
		if(max==-1)
			printf("Oh, my god\n");
		else
			printf("%d %d\n",east-max+1,east);
	}
}

 zoj_1128

#include<iostream>
#include<cstdio>
#include<vector>
#include<set>
using namespace std;
double lx,ly,rx,ry;
int n,size;
class rect
{
	public:
		double lx,ly,rx,ry;
		rect(double lx,double ly,double rx,double ry)
		{
			this->lx=lx;
			this->ly=ly;
			this->rx=rx;
			this->ry=ry;
		}
};
vector<rect>v;
set<double>x;
set<double>y;
bool cover(rect a)
{
	for(int i=0;i<size;i++)
	{
		if(a.lx>=v[i].lx&&a.rx<=v[i].rx&&a.ly>=v[i].ly&&a.ry<=v[i].ry)
		{
			return true;	
		}		
	}
	return false;
		
}
int main()
{
	int num=1;
	freopen("e:\\zoj\\zoj_1128.txt","r",stdin);
	while(cin>>n&&n)
	{
		v.clear();
		x.clear();
		y.clear();
		while(n--)
		{
			cin>>lx>>ly>>rx>>ry;
			x.insert(lx);
			x.insert(rx);
			y.insert(ly);
			y.insert(ry);
			v.push_back(rect(lx,ly,rx,ry));
		}
		double square=0;	
		size=v.size();
		for(set<double>::iterator it=x.begin();it!=x.end();++it)
		{
			lx=(*it);
			if(++it==x.end())
			break;
			rx=(*it);
			--it;
			for(set<double>::iterator it2=y.begin();it2!=y.end();++it2)
			{
				ly=(*it2);
				if(++it2==y.end())
				break;
				ry=(*it2);
				--it2;
				if(cover(rect(lx,ly,rx,ry)))
					square+=(rx-lx)*(ry-ly);			
			}
		}
		cout<<"Test case #"<<num<<endl;
		printf("Total explored area: %.2lf\n",square);
		printf("\n");
		++num;
	}		
}