/*
* 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( set, set + k );
sort(s, s+m);
m = unique_copy( s, s + m , t ) - t;
init( 1, 0, m - 1 );
b = lower_bound( t, t + m, set[0].b ) - t;
e = lower_bound( t, t + m, set[0].e ) - t;
add ( 1, 0, 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( 1, 0, m-1 );
}
b = lower_bound( t, t + m, set[i].b ) - t;
e = lower_bound( t, t + m, set[i].e ) - t;
add ( 1, 0, 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) 编辑 收藏 引用 所属分类:
模板