# HDU 1542 Atlantis ( Scanning Line, Segment Tree )

Problem - 1542

N ≤ 100

O( N lg^2 N ) / O( N lg N )

```#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100;

int N;
double L[ MAXN ], D[ MAXN ], R[ MAXN ], U[ MAXN ];
map< double, int > mp;
vector< double > dsctz;

struct segt{
int lb, rb;
int cov;
double cov_len;
segt *lc, *rc;
segt(){}
segt( int ll, int rr ){
lb = ll, rb = rr;
cov = 0;
cov_len = 0.0;
lc = rc = NULL;
}
void pull(){
if( cov ){
cov_len = dsctz[ rb ] - dsctz[ lb ];
return;
}
cov_len = ( lc ? lc->cov_len : 0.0 ) + ( rc ? rc->cov_len : 0.0 );
}
} *root;

void update( segt *t, int ql, int qr, int v ){
if( qr <= t->lb or t->rb <= ql ) return;
if( ql <= t->lb and t->rb <= qr ){
t->cov += v;
t->pull();
return;
}
int mid = t->lb + t->rb >> 1;
if( not t->lc ) t->lc = new segt( t->lb, mid );
update( t->lc, ql, qr, v );
if( not t->rc ) t->rc = new segt( mid, t->rb );
update( t->rc, ql, qr, v );
t->pull();
}

signed main(){
ios::sync_with_stdio( 0 );
for( int ti = 0; cin >> N and N; ++ti ){
double ans = 0.0;
dsctz.clear();
for( int i = 0; i < N; ++i ){
cin >> L[ i ] >> D[ i ] >> R[ i ] >> U[ i ];
dsctz.emplace_back( L[ i ] );
dsctz.emplace_back( R[ i ] );
}
{ // discretize
sort( dsctz.begin(), dsctz.end() );
dsctz.erase( unique( dsctz.begin(), dsctz.end() ), dsctz.end() );
mp.clear();
for( int i = 0; i < dsctz.size(); ++i ){
mp[ dsctz[ i ] ] = i;
}
}
{ // scanning line
vector< tuple< double, int, int, int > > event;
for( int i = 0; i < N; ++i ){
event.emplace_back( D[ i ], 0, mp[ L[ i ] ], mp[ R[ i ] ] );
event.emplace_back( U[ i ], 1, mp[ L[ i ] ], mp[ R[ i ] ] );
}
sort( event.begin(), event.end() );
root = new segt( 0, dsctz.size() - 1 );
for( int i = 0; i + 1 < 2 * N; ++i ){
double y; int t, lid, rid; tie( y, t, lid, rid ) = event[ i ];
update( root, lid, rid, t ? -1 : 1 );
ans += root->cov_len * ( get< 0 >( event[ i + 1 ] ) - y );
}
}
cout << "Test case #" << ti + 1 << "\n";
cout << "Total explored area: " << fixed << setprecision( 2 ) << ans << "\n\n";
}
return 0;
}
```