题目链接：

很经典的题目，网上有很多模板代码，自己理解了一天，然后很容易就敲出来了。。。

代码：

1 #include
     
        2 #include
      
         3 #include
       
          4 #include
        
           5 #include
         
            6 #define maxn 110  7 using namespace std;  8 int n;  9 class node 10 { 11    public: 12    int l,r;//端点坐标的映射值(整数值) 13    double cnt; 14    double c; 15    double lf,rf;//实际的端点坐标 16 }; 17 node segTree[maxn*3]; 18 class Line 19 { 20    public: 21    double x; 22    double y1; 23    double y2; 24    double f;//f=1表示左边，f=-1表示矩形的右边 25 }; 26 Line line[maxn]; 27 double y[maxn]; 28 bool cmp(Line a, Line b) 29 { 30     return a.x < b.x; 31 } 32 void Build(int num, int l, int r) 33 { 34    segTree[num].l=l; 35    segTree[num].r=r; 36    segTree[num].cnt=segTree[num].c=0; 37    segTree[num].lf=y[l]; 38    segTree[num].rf=y[r]; 39    if(l+1==r) return ; 40    int mid=(l+r)/2; 41    Build(num*2,l,mid); 42    Build(num*2+1,mid,r); 43 } 44 void calen(int num)//计算边的有效长度 45 { 46     if(segTree[num].c > 0) //表示当前边为直接有效部分 cnt存边的长度 47      { 48         segTree[num].cnt=segTree[num].rf-segTree[num].lf; 49         return ; 50      } 51    else//如果当前边不是直接有效部分 可以理解为当前边已经不存在 52      { 53         if(segTree[num].l+1 ==segTree[num].r) //如果当前边为最小的单元(就是没有孩子了),那么其间接有效长度为0 54         { 55             segTree[num].cnt=0; 56         } 57         else//否则其有效长度为孩子的有效长度和 58          { 59                segTree[num].cnt=segTree[num*2].cnt+segTree[num*2+1].cnt; 60                return ; 61          } 62  63      } 64 } 65 void Update(int num,Line e) 66 { 67     if(segTree[num].lf== e.y1 && segTree[num].rf ==e.y2) 68     { 69         segTree[num].c+=e.f; 70         calen(num); 71         return ; 72     } 73     if(segTree[num*2].rf>=e.y2) Update(num*2,e); 74     else 75        if(segTree[num*2+1].lf<=e.y1) Update(num*2+1,e); 76         else 77         { 78             Line tmp=e; 79             tmp.y2=segTree[num*2].rf; 80             Update(num*2,tmp); 81             tmp=e; 82             tmp.y1=segTree[num*2+1].lf; 83             Update(num*2+1,tmp); 84         } 85         calen(num); 86 } 87 int main() 88 { 89       int iCase=1; 90       double x1,x2,y1,y2; 91      while(scanf("%d",&n)!=EOF  && n) 92      { 93          int t=1; 94          for(int i=1;i<=n;i++) 95          { 96              scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2); 97              line[t].x=x1; 98              line[t].y1=y1; 99              line[t].y2=y2;100              line[t].f=1;101              y[t]=y1;102              t++;103              line[t].x=x2;104              line[t].y1=y1;105              line[t].y2=y2;106              line[t].f=-1;107              y[t]=y2;108              t++;109           }110          sort(y+1,y+t);111          sort(line+1,line+t,cmp);112          Build(1,1,t-1);113          Update(1,line[1]);114          double ans=0;115          for(int i=2;i