思路：

嗯哼，要开始利用线段树求解矩形面积的并、交、以及周长了。先看一下吧

给定一个矩形的左下角坐标和右上角坐标分别为:(x1,y1)、(x2,y2)，对这样的一个矩形，我们构造两条线段，一条定位在x1，它在y坐标的区间是[y1,y2]，并且给定一个cover域值为1；另一条线段定位在x2，区间一样是[y1,y2]，给定它一个cover值为-1。根据这样的方法对每个矩形都构造两个线段，最后将所有的线段根据所定位的x从左到右进行排序。

上图中，红色的字体表示的是该线段的cover值。刚刚开始的时候，线段树上的cover值都为0，但第一根线段(x==0)插入线段树的之后，我们将线段树上的cover加上该线段的cover，那么，此时线段树上被该线段覆盖的位置上的cover的值就为1，下次再插入第二根线段（x==1）此时发现该线段所覆盖的区间内，有一部分线段树的cover为0，另有一部分为1，仔细观察，但插入第二个线段的时候，如果线段树上cover已经为1的那些区间，和现在要插入的第二根线段之间，是不是构成了并面积？还不明白？看下图，绿色部分即为插入第二根线段后得到的并面积

够清楚了吧！也就是说，我们插入某跟线段的时候，只要看该线段所在区间上的cover是否大于等于1，如果是，那么就可以将并面积值加上(目前线段的x定位 - 上一线段的x定位)*（该区间的大小）

1255：

#include
     
      #include
      
       using namespace std;struct node {    double x,up,down;    int flag;}link[2005];struct {    double x,up,down;    int cover,child;}tree[1000000];double yy[2005];int cmp(const double &a,const double &b){    if(a
       
        =tree[i].up)        return 0;    if(!tree[i].child)    {        if(tree[i].cover>1)        {            double ans=0;            ans=(x-tree[i].x)*(tree[i].up-tree[i].down);            tree[i].cover+=flag;            tree[i].x=x;            return ans;        }        else        {            tree[i].cover+=flag;            tree[i].x=x;            return 0;        }    }    return updata(i*2,l,r,x,flag)+updata(i*2+1,l,r,x,flag);}int main(){    int t;    scanf("%d",&t);    while(t--)    {        int n;        scanf("%d",&n);        int i,j=1;        for(i=1;i<=n;i++)        {            double x1,y1,x2,y2;            scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);            link[j].x=x1;            link[j].up=y2;            link[j].down=y1;            link[j].flag=1;            yy[j]=y1;            j++;            link[j].x=x2;            link[j].up=y2;            link[j].down=y1;            link[j].flag=-1;            yy[j]=y2;            j++;        }        sort(yy+1,yy+j,cmp);        sort(link+1,link+j,cmp1);        build(1,1,j-1);        double ans=0;        for(i=1;i
       
      
     

 1542：

1 #include
      
         2 #include
       
          3 using namespace std;  4 struct node  5 {  6     double x,up,down;  7     int flag;  8 }link[10000];  9 struct node1 10 { 11     double x,up,down; 12     int cover,child; 13 }tree[100000]; 14 double yy[10000]; 15 int cmp(const double &a,const double &b) 16 { 17     if(a
        
         =tree[i].up) 48         return 0; 49     if(!tree[i].child) 50     { 51         if(tree[i].cover>0) 52         { 53             double ans=0; 54             ans+=(x-tree[i].x)*(tree[i].up-tree[i].down); 55             tree[i].x=x; 56             tree[i].cover+=flag; 57             return ans; 58         } 59         else 60         { 61             tree[i].x=x; 62             tree[i].cover+=flag; 63             return 0; 64         } 65     } 66     return updata(i*2,down,up,flag,x)+updata(i*2+1,down,up,flag,x); 67 } 68 int main() 69 { 70     int n,f=0,i; 71     while(scanf("%d",&n)>0&&n) 72     { 73         int j=1; 74         for(i=1;i<=n;i++) 75         { 76             double x1,y1,x2,y2; 77             scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2); 78             link[j].x=x1; 79             link[j].down=y1; 80             link[j].up=y2; 81             link[j].flag=1; 82             yy[j]=y1; 83             j++; 84             link[j].x=x2; 85             link[j].down=y1; 86             link[j].up=y2; 87             link[j].flag=-1; 88             yy[j]=y2; 89             j++; 90         } 91         sort(yy+1,yy+j,cmp); 92         sort(link+1,link+j,cmp1); 93         j--; 94         double ans=0; 95         build(1,j,1); 96         for(i=1;i<=j;i++) 97         { 98             ans+=updata(1,link[i].down,link[i].up,link[i].flag,link[i].x); 99         }100         printf("Test case #%d\n",++f);101 102         printf("Total explored area: %.2lf\n\n",ans);103     }104     return 0;105 }