#include  < iostream >
#include 
< algorithm >

using   namespace  std;

#define  N 211

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

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 , mid;
    
while ( low <=  high ) {
        mid
=  (low +  high) >>   1 ;
        
if ( idx[mid] >  value ) high =  mid -   1 ;
        
else   if ( idx[mid] <  value ) low =  mid +   1 ;
        
else   return  mid;
    }

}


void  insert(  int  rt,  int  l,  int  r,  int  a,  int  b ) {
    
if ( l ==  a  &&  r ==  b ) {
        tb[rt].length
=  idx[r] -  idx[l];
        tb[rt].cnt
++ return ; }

    
    
if ( tb[rt].cnt !=   0  ) {
        tb[rt
<< 1 ].cnt +=  tb[rt].cnt; tb[(rt << 1 ) + 1 ].cnt +=  tb[rt].cnt;
        tb[rt].cnt
=   0 ;
    }

    
    
int  mid =  (l +  r) >>   1 ;
    
if ( b <=  mid ) insert( rt <<   1 , l, mid, a, b );
    
else   if ( a >=  mid ) insert( (rt << 1 ) +   1 , mid, r, a, b );
    
else {
        insert( rt
<<   1 , l, mid, a, mid );
        insert( (rt
<< 1 ) +   1 , mid, r, mid, b ); }

    
    
if ( tb[rt].cnt >   0  ) tb[rt].length =  idx[r] -  idx[l];
    
else  tb[rt].length =  tb[rt << 1 ].length +  tb[(rt << 1 ) + 1 ].length;
}


void  del(  int  rt,  int  l,  int  r,  int  a,  int  b ) {
    
if ( l ==  a  &&  r ==  b ) {
        tb[rt].cnt
-- ;   return ;
    }

    
    
if ( tb[rt].cnt !=   0  ) {
        tb[rt
<< 1 ].cnt +=  tb[rt].cnt; tb[(rt << 1 ) + 1 ].cnt +=  tb[rt].cnt;
        tb[rt].cnt
=   0 ;
    }

        
    
int  mid =  (l +  r) >>   1 ;
    
if ( b <=  mid ) del( rt <<   1 , l, mid, a, b );
    
else   if ( a >=  mid ) del( (rt << 1 ) +   1 , mid, r, a, b );
    
else {
        del( rt
<<   1 , l, mid, a, mid );
        del( (rt
<< 1 ) +   1 , mid, r, mid, b );    
    }

}


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

    
    
if ( tb[rt].cnt !=   0  ) {
        tb[rt
<< 1 ].cnt +=  tb[rt].cnt; tb[(rt << 1 ) + 1 ].cnt +=  tb[rt].cnt;
        tb[rt].cnt
=   0 ;
    }

    
    
int  mid =  ( l +  r ) >>   1 ;
    query( rt
<< 1 , l, mid );
    query( (rt
<< 1 ) +   1 , mid, r );
    
    tb[rt].length
=  tb[rt << 1 ].length +  tb[(rt << 1 ) + 1 ].length;
}


int  main() {
    
int  test =   1 ;
    
while ( scanf( " %d " , & n), n !=   0  ) {
        
for int  i =   0 ; i <=   1600 ++ 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  ) insert(  1 1 , pos, u, v );
            
else  del(  1 1 , pos, u, v );
            
            query( 
1 1 , pos );
            ans
+=  tb[ 1 ].length *  ( line[i + 1 ].y -  line[i].y );
        }

        
        printf(
" Test case #%d\n " , test ++  );
        printf(
" Total explored area: %.2lf\n\n " , ans );
    }

    
    
return   0 ;
}






#include  < iostream >
#include 
< algorithm >

using   namespace  std;

#define  N 211

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

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 >   0  ) 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;
}

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 );  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 );
}

int  main(){
    
int  test =   1 ;
    
while ( scanf( " %d " , & n), n !=   0  ){
        
for int  i =   0 ; i <=   800 ++ 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 ].length *  ( line[i + 1 ].y -  line[i].y );
        }
        printf(
" Test case #%d\n " , test ++  );
        printf(
" Total explored area: %.2lf\n\n " , ans );
    }
    
    
return   0 ;
}
posted on 2009-08-06 00:49 Darren 阅读(477) 评论(0)  编辑 收藏 引用 所属分类: 数据结构

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