Atcoder Regular Contest 076 E. Connected?

Atcoder Regular Contest 076 E. Connected?

E: Connected? - AtCoder Regular Contest 076 | AtCoder

感想

だいぶ前に線分の交差判定などで解こうとしたけどダメだったので放置していた。条件をもう少し本質的にとらえることと、周を1次元に落とし込むことの両方ができていなかった。

解法

まず線分の少なくとも一方の端点が長方形の周上にない場合は、この線分はないものとして考えて良い（他の線分を妨げることがないため）。

端点が両方周上にあるものについて、その端点を$\ A\ $と$\ a\ $というようなペアで考える。このとき、周上のある点からぐるっと一周しながら点をみていったときに、$\ A, B, a, b\ $というような順番になっていればこれらの一方はどうしても結ぶことができない。逆に、うまく結ぶことができる順番というのは、かっこ（）を矛盾なく組み合わせたような順番である。例えば（（（））（））が$\ A, B, C, c, b, D, d, a\ $などに対応する。ここまで考えるとあとはstackで簡単に書ける。

実装は簡単。

実装

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

#define all(x)  x.begin(), x.end()
#define mp      make_pair
#define pii     pair<int, int>

int h, w;

bool on(int y, int x) {
        if (x == 0 || x == w || y == 0 || y == h) return true;
        return false;
}

int convert(int y, int x) {
        if (x == 0) return y;
        if (y == h) return h + x;
        if (x == w) return h + w + h - y;
        if (y == 0) return h + w + h + w - x;
        assert(0);
}

int main() { int n;
        cin >> h >> w >> n;
        vector<pii> pos;
        for (int i = 0; i < n; i ++) {
                int y1, x1, y2, x2;
                cin >> y1 >> x1 >> y2 >> x2;
                if (on(y1, x1) && on(y2, x2)) {
                        pos.push_back(mp(convert(y1, x1), i));
                        pos.push_back(mp(convert(y2, x2), i));

                }
        }
        sort(all(pos));
        stack<int> st;
        for (int i = 0; i < pos.size(); i ++) {
                if (st.empty() || st.top() != pos[i].second) st.push(pos[i].second);
                else st.pop();
        }
        cout << (st.empty() ? "YES" : "NO") << endl;
        return 0;
}