E - Connected?

E - Connected?

よく考えると端同士が繋がれてるもののみ考えればいいとわかる
その中で、全ての線が交わらなければYes

時計回りで見た時に123321のように対応が取れていれば繋げるため、スタックの要領で溶ける

(kmjpさんのコード参考)
Submission #4184430 - AtCoder Regular Contest 076

vi a, b, c;
vp p;
int id(P a) {
    int x = a.fi, y = a.se;
    if (x == 0)return y;
    if (y == h)return 1e9 + x;
    if (x == w)return 2 * 1e9 + h - y;
    if (y == 0)return 3 * 1e9 + w - x;
    return -1;
}
signed main() {
    cin >> w >> h >> n;
    rep(i, n) {
        P f, t;
        cin >> f >> t;
        int x = id(f);
        int y = id(t);
        if (x == -1 || y == -1)continue;
        p.eb(x, i);
        p.eb(y, i);
    }
    sort(p);
    n = s(p);
    rep(i, n) {
        if (s(a) && a.back() == p[i].se) {
            a.pop_back();
        } else {
            a.pb(p[i].se);
        }
    }
    YN(s(a) == 0);
    return 0;
}