线段染色,矩形切割，离散化---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<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;}}?