問題概要
円周上に $2n$ 個の点が並んでいて，（適当な位置から）時計回りに $1, 2, \dots, 2 n$ で番号付けられている．円周上には $n$ 本の「弦」*1があり，$i$ 番目の弦は点 $A_i$ と $B_i$ を結んでいる．この弦たちはその端点以外で交点をもつか？
制約
- $2 \leq n \leq 2 \times 10^5$
解法
まずは $2$ つの弦が交点をもつ条件について考えてみます．ひとつの弦の端点を $a, a'$ ，もうひとつの弦の端点を $b, b'$ として，円周上での出現順序について考えますが，
- 先に出現した方を「$'$」が付かない方とする
- $a, b$ を入れ替える対象性は無視する
とすると，あり得るパターンは
- $a a' b b'$
- $a b a' b'$
- $a b b' a'$
の $3$ 通りです．この内，交点をもつのは真ん中のパターンとなります．観察してみると，
- ある弦の端点を見た後に，
- 別の弦の端点を見て，
- ひとつ目の端点の片割れより前に，ふたつ目の端点の片割れを見た
場合に交点があると言えます．また，それぞれの列をどのように回転*2させても交点の有無が変化しないことも確かめられます．このことから，（証明がてけとーですが*3），円周上の適当な位置から適当な方向に走査して，括弧列に対するアルゴリズムと同じようにスタックを利用して validness を調べるというアルゴリズムが考えられます．
このアルゴリズムは，$2 n$ 個の点に対して高々 $1$ 回ずつスタック操作を行うので，$\Theta( n )$ 時間で動作します．
コード
int main() { IN( int, N ); VI A( N ), B( N ); REP( i, N ) { cin >> A[i] >> B[i]; --A[i], --B[i]; } VI circle( 2 * N ); REP( i, N ) { circle[ A[i] ] = B[i]; circle[ B[i] ] = A[i]; } map< PII, int > counts; stack< PII > stk; FOR( a, circle ) { const int b = circle[a]; const PII chord = minmax( a, b ); if ( counts[ chord ]++ == 0 ) { stk.push( chord ); } else { if ( stk.top() != chord ) { cout << "Yes" << endl; return 0; } stk.pop(); } } cout << "No" << endl; return 0; }
