HDU 1542 Atlantis ( Scanning Line, Segment Tree )
題意:
給很多矩形的左下角和右上角座標,問聯集面積為何。
資料規模:
座標為有理數
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; }