ARC076 E. Connected?

問題

x,y座標の(0,0)から(R,C)までの長方形を考える。
N個の長方形内の点のペアが与えられる。(各点はすべて異なる)
ペアの点同士を曲線で結びたい。ただし、長方形の外に出たり、交わってはいけない。
可能かどうか判定せよ。

制約

1 <= R,C <= 10^8
1 <= N <= 10^5

解説

Editorial - AtCoder Regular Contest 076 | AtCoder

いくつかサンプルを図で書いてみると、「ペアの点がどちらも長方形の周上にある場合、領域を2分割してしまって、それぞれ異なる領域にある点はどうやっても交差してしまう」というのがわかる。
そうでない場合は、曲線をうまく調整することで交差しないように書くことができることがわかる。

周上を1直線として見て、領域がoverlapしていないかを判定すればよい。

これは、「対応のある括弧の整合性判定(「((()()())((()()())))」みたいなの)」ともみなせるので、stackを使って判定すればよい。

反省

領域のoverlapの判定で、普通にミスってしまった。

領域を周上の座標にマッピングしたとき(l,r)とすると、l側でソートしておき、rをstackに入れながら処理していて、
今(l,r)を考えていて、直前のスタックにあるのがprとすると、

• l < prの場合、かつ、pr < rの場合、オーバーラップしている
• l < prの場合、かつ、r < prの場合、領域内にいるので、prとrをスタックに積んで次へ
• pr < lの場合、新しい領域に入っているので、rだけスタックに積んで次へ

というやり方をしてしまった。
これだと処理が一つ抜けていて、例えば(1,5)、(2,3)、(4,6)のような場合、(2,3)の処理をした後、5と3がスタックに積まれているが、(4,6)を処理するとき、prで考えるべきは5と3両方なのに、3だけ確認して処理して、スタックに5と6みたいな処理をしてしまう。
なので、pr < lの時は、スタックからl < prになるまで全部取り出してあげる必要がある。

  stack<ll> st;
  st.push(R+R+C+C);
  int i=0;
  while(i<v.size()){
    ll l = v[i].l;
    ll r = v[i].r;
    ll pr = st.top(); st.pop();
    if(pr < l) continue;
    if(r<pr){
      st.push(pr);
      st.push(r);
    }
    else if(pr<r){
      cout << "NO" << endl;
      return 0;
    }
    i++;
  }
  cout << "YES" << endl;