問題概要
平面上に，$Y$ 軸に平行な線分が $N$ 本，$X$ 軸に平行な線分が $M $ 本引かれている．$i$ 番目の縦線は 2 点 $( A_i, C_i )$ と $( B_i, C_i )$ を結んでいて，$j$ 番目の横線は 2 点 $( D_j, E_j )$ と $( D_j, F_j )$ を結んでいる．
原点からスタートして平面状を歩くとき，いずれの線分も跨がずに行ける領域の面積を求めよ．無限に広い場合は，代わりに "INF" と出力せよ．
制約
- 座標の絶対値は $10^9$ 以下で，整数
- $1 \leq N, M \leq 1{,}000$
- $A_i < B_i$
- $E_j < F_j$
- 原点を通る線分は無い
解法
線分が軸に平行かつ整数なので，平面をグリッド状に刻んで考えることができます．ここでは，各グリッドをその左上の座標によって識別することにします（例えば，原点はその右下のグリッドに含まれていることにする（$Y$ 軸を下向きにとります））．
問われている面積を求めるだけであれば，原点を含むグリッドからスタートして BFS などをすることで求めることができますが，（意味のある）空間がそれなりに広いため，これでは TLE します．しかしよく考えてみると，空間を広くとったとき，広さに対して線分の本数がかなり少なくなるため，中身は「スカスカ」になります．このときにできる「変化の起こらない領域」をひとまとめにして扱うことで，探索空間を $O( N M )$ ぐらいのサイズにすることができます．
具体的には，線分の端点及び原点の座標を軸ごとにソート + unique することで，ソート後に隣接する座標値の間にはその軸に関して「何も無い」というような状態を作れます．これは「座標圧縮」として知られていて，蟻本 [1] にも記載がありますので，そちらもご参照ください．
今回の問題で座標圧縮をすると，グリッドはいくつかの長方形領域に区切られて，それぞれの辺は「全て線分に乗っている」か「（端点を除いて）全く線分に乗っていない」かのいずれかになります*1．なので，座標圧縮をした跡の各領域について，その境界を跨げるかどうかを判定できるようにしておくと BFS などをすることができます．無限大かどうかの判定については，外平面まで歩けるかどうかを調べられれば良いので，樹部分大きい値を座標に加えることで外平面を表現し，そこに行けるかどうかで判定できます．
以下の参考実装では Disjoint Set Forest (Union-FInd) を使って横着をしていますので，$O( N M \alpha( NM ) )$ 時間です．
コード
constexpr auto INF = LIM<>::max() / 2; class DisjointSetForest; // DisjointSetForest( N ) // find( x ) // same( x, y ) // unite( x, y ) // groups() // groupSize( x ) VI compress( const VI &a, const VI &b, const VI &c ) { VI res{ -INF, 0, INF }; copy( ALL( a ), BI( res ) ); copy( ALL( b ), BI( res ) ); copy( ALL( c ), BI( res ) ); sort( ALL( res ) ); res.erase( unique( ALL( res ) ), end( res ) ); return res; } int main() { cin.tie( 0 ); ios::sync_with_stdio( false ); cout << setprecision( 12 ) << fixed; IN( int, N, M ); VI A( N ), B( N ), C( N ), D( M ), E( M ), F( M ); REP( i, N ) { cin >> A[i] >> B[i] >> C[i]; } REP( i, M ) { cin >> D[i] >> E[i] >> F[i]; } const VI ys = compress( A, B, D ); const VI xs = compress( C, E, F ); const int H = SZ( ys ); const int W = SZ( xs ); VVI right_bounded( H, VI( W ) ), down_bounded( H, VI( W ) ); REP( i, N ) { const int idx_x = --lower_bound( ALL( xs ), C[i] ) - begin( xs ); const int idx_y1 = lower_bound( ALL( ys ), A[i] ) - begin( ys ); const int idx_y2 = lower_bound( ALL( ys ), B[i] ) - begin( ys ); REP( j, idx_y1, idx_y2 ) { right_bounded[j][ idx_x ] = true; } } REP( i, M ) { const int idx_y = --lower_bound( ALL( ys ), D[i] ) - begin( ys ); const int idx_x1 = lower_bound( ALL( xs ), E[i] ) - begin( xs ); const int idx_x2 = lower_bound( ALL( xs ), F[i] ) - begin( xs ); REP( j, idx_x1, idx_x2 ) { down_bounded[ idx_y ][j] = true; } } DisjointSetForest dsf( H * W ); const auto grid_id = [&]( const int y, const int x ) { return y * W + x; }; REP( i, H ) { REP( j, W ) { if ( i + 1 < H && !down_bounded[i][j] ) { dsf.unite( grid_id( i, j ), grid_id( i + 1, j ) ); } if ( j + 1 < W && !right_bounded[i][j] ) { dsf.unite( grid_id( i, j ), grid_id( i, j + 1 ) ); } } } const int idx_y0 = lower_bound( ALL( ys ), 0 ) - begin( ys ); const int idx_x0 = lower_bound( ALL( xs ), 0 ) - begin( xs ); if ( dsf.same( 0, grid_id( idx_y0, idx_x0 ) ) ) { cout << "INF" << endl; return 0; } LL res = 0; REP( i, H ) { REP( j, W ) { if ( !dsf.same( grid_id( i, j ), grid_id( idx_y0, idx_x0 ) ) ) { continue; } const LL dy = ys[ i + 1 ] - ys[i]; const LL dx = xs[ j + 1 ] - xs[j]; res += dy * dx; } } cout << res << endl; return 0; }
参考文献
[1] 秋葉拓哉, 岩田陽一, and 北川宜稔. プログラミングコンテストチャレンジブック: 問題解決のアルゴリズム活用力とコーディングテクニックを鍛える. マイナビ出版, 2012.
*1:辺ごとに乗っていたり乗っていなかったりします．一応
