0w1

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