AtCoder Regular Contest 076: E - Connected?

,

https://beta.atcoder.jp/contests/arc076/tasks/arc076_c

$R$と$C$は逆にしたいなあと思う

solution

どちらか一方以上が周上に乗っていない対は無視してよい。 平面上でなく環上に乗っている、特に両端が繋がった数列と見てよい。 NOになるのは入力例$4$のように交差があるとき。 環状の数列上で同じ数字が隣り合っていれば消すことを繰り返し、全て消せるか判定すればよい。$O(N)$。

implementation

#!/usr/bin/env python3
w, h, n = map(int, input().split())
def proj(x, y):
    if y == 0:
        return x
    elif x == w:
        return w + y
    elif y == h:
        return w + h + (w - x)
    elif x == 0:
        return w + h + w + (h - y)
    else:
        return None
ps = []
for i in range(n):
    x1, y1, x2, y2 = map(int, input().split())
    p1 = proj(x1, y1)
    p2 = proj(x2, y2)
    if p1 is not None and p2 is not None:
        ps += [ (p1, i), (p2, i) ]
ps.sort()
stk = []
for _, i in ps:
    if stk and stk[-1] == i:
        stk.pop()
    else:
        stk.append(i)
result = not stk
print([ 'NO', 'YES' ][ result ])