#include  < iostream >
#include 
< algorithm >

using   namespace  std;

#define  N 2110

struct  Tree {
    
double  length, len;
    
int     cnt;
    Tree()
{ length =   0 ; cnt =   0 ; }
    
void  init() { length =   0 ; cnt =   0 ; len =   0 ; }
}
tb[ 10100 ];

double  x1[N], y1[N], x2[N], y2[N], xx[N], idx[N];
int  pos, n;

struct  Line {
    
double  y, x1, x2;
    
bool  type;
}
line[N];

bool   operator < ( Line  const &  a, Line  const &  b ) {
    
return  a.y <  b.y; }

    
inline 
int  bsearch(  double  value ) {
    
int  low =   1 , high =  pos +   1 ;
    
while ( low <=  high ) {
        
int  mid =  (low +  high) >>   1 ;
        
if ( idx[mid] >  value ) high =  mid -   1 ;
        
else   if ( idx[mid] <  value ) low =  mid +   1 ;
        
else   return  mid; }

}


inline 
void  update(  int  rt,  int  l,  int  r ) {
    
if ( tb[rt].cnt ) tb[rt].length =  idx[r] -  idx[l];
    
else   if ( l +   1 ==  r ) tb[rt].length =   0 ;
    
else  tb[rt].length =  tb[rt << 1 ].length +  tb[(rt << 1 ) + 1 ].length;
}


inline 
void  update2(  int  rt,  int  l,  int  r ) {
    
if ( tb[rt].cnt >   1  ) tb[rt].len =  idx[r] -  idx[l];
    
else   if ( tb[rt].cnt ==   1  ) tb[rt].len =  tb[rt << 1 ].length +  tb[(rt << 1 ) + 1 ].length;
    
else  tb[rt].len =  tb[rt << 1 ].len +  tb[(rt << 1 ) + 1 ].len; }


void  deal(  int  rt,  int  l,  int  r,  int  a,  int  b,  int  t ) {
    
if ( a <=  l  &&  b >=  r ) {
        tb[rt].cnt
+=  t; update( rt, l, r ); update2( rt, l, r );   return ; }

        
    
int  mid =  (l +  r) >>   1 ;
    
if ( a <  mid ) deal( rt <<   1 , l, mid, a, b, t);
    
if ( b >  mid ) deal( (rt << 1 ) +   1 , mid, r, a, b, t );
    
    update( rt, l, r ); update2( rt, l, r );
}


int  main() {
    
int  test =   1 ;
    scanf(
" %d " , & test );
    
while ( test --  ) {
        scanf(
" %d " , & n);
        
for int  i =   0 ; i <=   10000 ++ i ) tb[i].init();
        
for int  i =   0 ; i <  n;  ++ i )  {
            scanf(
" %lf%lf%lf%lf " , x1 +  i, y1 +  i, x2 +  i, y2 +  i );
            line[
2 * i].y =  y1[i];   line[ 2 * i].x1 =  x1[i]; 
            line[
2 * i].x2 =  x2[i];  line[ 2 * i].type =   0 ;
            
            xx[
2 * i] =  x1[i]; xx[ 2 * i +   1 ] =  x2[i];
            line[
2 * i + 1 ].y =  y2[i];  line[ 2 * i + 1 ].x1 =  x1[i];
            line[
2 * i + 1 ].x2 =  x2[i]; line[ 2 * i + 1 ].type =   1 ;
        }

        sort( xx, xx
+   2 *  n );    sort( line, line +   2 *  n );
        pos
=   1 ; idx[ 1 ] =  xx[ 0 ];
        
for int  i =   1 ; i <   2 *  n;  ++ i )
        
if ( xx[i] !=  xx[i - 1 ] ) idx[ ++ pos] =  xx[i];
        
        
double  ans =   0 ;
        
for int  i =   0 ; i <   2 *  n -   1 ++ i ) {
            
int  u =  bsearch( line[i].x1 ), v =  bsearch( line[i].x2 );
            
if ( line[i].type ==   0  ) deal(  1 1 , pos, u, v,  1  );
            
else  deal(  1 1 , pos, u, v,  - 1  );
            
            ans
+=  tb[ 1 ].len *  ( line[i + 1 ].y -  line[i].y );
        }

        printf(
" %.2lf\n " , ans );
    }

    
    
return   0 ;
}

posted on 2009-08-06 09:59 Darren 阅读(583) 评论(0)  编辑 收藏 引用 所属分类: 数据结构

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理