posts - 2,comments - 1,trackbacks - 0
/* 
 * File:   newmain.cpp
 * Author: ok
 * 
 * Created on November 3, 2009, 3:00 PM
 * 坐标离散化,矩形面积并
 
*/

#include 
<iostream>
#include 
<algorithm>
#include 
<stdio.h>
#include 
<stdlib.h>

using namespace std;

const int N = 1000005;
double lx[N], ly[N], rx[N], ry[N];

struct line{
    
int flag ;
    
double b,e,x;
    
bool operator < ( line t )const{
        
return x < t.x || x == t.x && flag > t.flag;
    }
}
set[N*2];

int id[N*2];
double s[N*2],t[N*2];
int node[N*6];
//int cnt[N*6]; 小数据的时候有所作用

void init( int id, int b, int e ){

    
if ( b == e )
        
return ;
    node[id] 
= 0;
    
//cnt[id] = 0;
    if ( b + 1 == e )
        
return ;
    
int m = ( b + e ) / 2;
    init( id 
* 2, b, m );
    init( id 
* 2 + 1, m, e );
}

void add( int id, int b, int e, int nb, int ne, int f ){
    
if ( b == e )
        
return ;
    
if ( nb >= e || ne <= b )
        
return ;
    
//cnt[id] += f;
    if ( nb <= b && e <= ne ){
        node[id] 
+= f;
        
return ;
    }
    
if ( b + 1 == e )
        
return ;
    
int m = ( b + e ) / 2;
    add( id 
* 2, b, m, nb, ne, f );
    add( id 
* 2 + 1, m, e, nb, ne, f );
}

double query( int id, int b, int e ){
    
if ( b == e )       return 0;
    
//if ( !cnt[id] )   return 0;
    if ( node[id] )      return t[e] - t[b];
    
if ( b + 1 == e ) return 0;
    
int m = ( b + e ) / 2;
    
return query( id * 2, b, m ) + query( id * 2 + 1, m, e );
}

int main(){
    
int i, j, k, n, m, z = 0;
    line now;
    
while ( scanf("%d",&n) != EOF && n ){
        k 
= 0; m = 0;
        
for ( i = 0 ; i < n ; i ++ ){
            scanf(
"%lf%lf%lf%lf",&lx[i],&ly[i],&rx[i],&ry[i]);
        }
        
for ( i = 0 ; i < n ; i ++ ){
            now.flag 
= 1; now.x = lx[i]; now.b = ly[i]; now.e = ry[i];
            
set[ k ++ ] = now;
            now.flag 
=-1; now.x = rx[i];
            
set[ k ++ ] = now;
            s[ m 
++ ] = ly[i]; s[ m ++ ] = ry[i];
        }
        
        
int b, e;
        
double ans = 0;

        sort( 
setset + k );
        sort(s, s
+m);
        
        m 
= unique_copy( s, s + m , t ) - t;
        
        init( 
10, m - 1 );
        
        b 
= lower_bound( t, t + m, set[0].b ) - t;
        e 
= lower_bound( t, t + m, set[0].e ) - t;
        
        add ( 
10, m - 1, b, e, 1);
        
for ( i = 1 ; i < k ; i ++ ){
            
if ( set[i].x - set[i-1].x != 0 ){
                ans 
+= (set[i].x - set[i-1].x ) * query( 10, m-1 );
            }
            b 
= lower_bound( t, t + m, set[i].b ) - t;
            e 
= lower_bound( t, t + m, set[i].e ) - t;
            add ( 
10, m - 1, b, e, set[i].flag );
        }
        printf(
"Test case #%d\nTotal explored area: %.2lf\n\n",++z,ans);
    }
    
return 0;
}

/*
2
1 1 2 2
3 3 4 4
2
1 1 2 2
2 2 4 4
2
1 1 2 2
2 1 3 2
3
0 0 1 1
0 2 3 3
2 4 3 5
*/
posted on 2009-11-02 22:17 Huicpc217 阅读(520) 评论(0)  编辑 收藏 引用 所属分类: 模板

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