给出一列矩形,求被矩形覆盖的面积总共有多少?

显然,最简单的办法就是模拟.设置一个布尔型二维数组,将有矩形覆盖的方格填上1,最后统计一遍即可.

但是复杂度相当可惜,和坐标系面积和举行个数以及矩形平均面积成正比.也就是说,如果坐标系范围在[-10000000,10000000]之间,就肯定过不了了.不仅过不了,而且存不下.10000x10000都困难.

有什么办法可以解决呢?注意n的值不大,所以有很多坐标数字都是不必须的,那么让我们"压缩"坐标系,将所有出现过的坐标都记录到一个hash数组中,那么就可以达到离散化的作用了.

附:color代码

#include #include struct rect{	int x1,x2,y1,y2,size,id;} rects[100];inline bool cmp(rect a,rect b){	return (a.size>b.size?true:(a.size==b.size?(a.id
     
      x1+=15000;		(rects+i)->x2+=15000;		(rects+i)->y1+=15000;		(rects+i)->y2+=15000;		xs[(rects+i)->x1]=1;		xs[(rects+i)->x2]=1;		ys[(rects+i)->y1]=1;		ys[(rects+i)->y2]=1;	}	xs[0]=ys[0]=1;	xs[30000]=ys[30000]=1;	j=0;	for(i=0;i<=30000;++i) if(xs[i]) xp[(xs[i]=j++)]=i;	xa=j;	j=0;	for(i=0;i<=30000;++i) if(ys[i]) yp[(ys[i]=j++)]=i;	ya=j;	for(i=0;i
      
       x1=xs[(rects+i)->x1];		(rects+i)->x2=xs[(rects+i)->x2];		(rects+i)->y1=ys[(rects+i)->y1];		(rects+i)->y2=ys[(rects+i)->y2];		for(xx=rects[i].x1;xx