AtCoder ARC 076 E - Connected? (2D, 黄色, 700 点)

面白かった！　交差数に関する問題に帰着される。

• 問題へのリンク

問題概要

座標平面上に、4 頂点の座標が であるような長方形があり、その長方形の周上または内部に、 とラベルのついた 個の点がある（どの 2 点も相異なる）。

について、同じラベル の 2 点を結んだ曲線を長方形の内部に引く。

このとき、 本の曲線のうち、どの 2 本も交差がないようにできるかどうかを判定せよ。

制約

• 

考えたこと

これ実は、長方形の周上にない点（内部）は関係ないのでは......と考えた。具体的には、同じラベルのついた 2 点のうち、片方または両方が長方形の周上にはないとき、その 2 点は無いものとして考えても良さそうだ。

証明は難しそうだったが、そう考えて解くことにして、解けた。ちゃんとした証明は editorial にある。もし 2 点とも長方形の周上にあるラベルのみ考えたときに、交差しないように曲線を引くことができるのならば、片方以上が長方形の周上にはないようなラベルを加えても、交差させずに済むことを示していた。

さて、長方形の周上の点に考察の対象が絞られたならば、次の問題と一緒だ。stack を用いて の計算量で解ける（点のソートに の計算量を要する）。

drken1215.hatenablog.com

コード

#include <bits/stdc++.h>
using namespace std;
using pint = pair<int, int>;

int main() {
    int R, C, N;
    cin >> R >> C >> N;

    auto calc = [&](int x, int y) -> int {
        if (x != 0 && x != R && y != 0 && y != C) return -1;
        if (x == 0) return y;
        else if (y == C) return C + x;
        else if (x == R) return R + C + (C - y);
        else return (R + C) * 2 - x;
    };

    vector<pint> points;
    for (int i = 0; i < N; i++) {
        int x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        int pos1 = calc(x1, y1), pos2 = calc(x2, y2);
        if (pos1 == -1 || pos2 == -1) continue;
        points.emplace_back(pos1, i);
        points.emplace_back(pos2, i);
    }
    sort(points.begin(), points.end());

    vector<int> st;
    for (auto [pos, id] : points) {
        if (!st.empty() && st.back() == id) st.pop_back();
        else st.push_back(id);
    }
    cout << (st.empty() ? "YES" : "NO") << endl;
}