AtCoder ABC 338 E - Chords (1Q, 緑色, 500 点)

弦が交わるかどうかを判定するという、スタックの典型問題！

• 問題へのリンク

問題概要

次の図のように、円周上に 個の点 があり、 本の弦がある（図は のとき）。

弦に交差があるかどうかを判定せよ。

制約

• 

考えたこと

この問題は stack で解けることで有名だ。次のようにして、カッコ列整合性判定問題へと帰着できる。

点 の順に、

• はじめて見る弦の端点であるとき、左カッコ '(' に対応させる
• すでに見た弦の端点であるとき、右カッコ ')' に対応させる

というようにしてできる、長さ のカッコ列を考える。このとき

---

弦に交差がない ⇔ カッコ列が整合する

---

となるのだ。よって、カッコ列の整合性を判定すればよいので、スタックを用いて計算量は となる。

コード

#include <bits/stdc++.h>
using namespace std;

int main() {
    int N, A, B;
    cin >> N;
    vector<int> partner(N * 2);
    for (int i = 0; i < N; i++) {
        cin >> A >> B, A--, B--;
        partner[A] = B, partner[B] = A;
    }

    vector<int> st;
    for (int i = 0; i < N*2; i++) {
        if (!st.empty() && partner[i] == st.back()) st.pop_back();
        else st.push_back(i);
    }
    cout << (!st.empty() ? "Yes" : "No") << endl;
}