Problem:


Score : 700 points

Problem Statement

Snuke is playing a puzzle game.
In this game, you are given a rectangular board of dimensions R × C, filled with numbers. Each integer i from 1 through N is written twice, at the coordinates (x_{i,1},y_{i,1}) and (x_{i,2},y_{i,2}).

The objective is to draw a curve connecting the pair of points where the same integer is written, for every integer from 1 through N.
Here, the curves may not go outside the board or cross each other.

Determine whether this is possible.

Constraints

1 ≤ R,C ≤ 10^8

1 ≤ N ≤ 10^5

0 ≤ x_{i,1},x_{i,2} ≤ R(1 ≤ i ≤ N)

0 ≤ y_{i,1},y_{i,2} ≤ C(1 ≤ i ≤ N)

All given points are distinct.

All input values are integers.

Input

Input is given from Standard Input in the following format:

R C N
x_{1,1} y_{1,1} x_{1,2} y_{1,2}
:
x_{N,1} y_{N,1} x_{N,2} y_{N,2}

Output

Print YES if the objective is achievable; print NO otherwise.

Sample Input 1

4 2 3
0 1 3 1
1 1 4 1
2 0 2 2

Sample Output 1

YES

The above figure shows a possible solution.

Sample Input 2

2 2 4
0 0 2 2
2 0 0 1
0 2 1 2
1 1 2 1

Sample Output 2

NO

Sample Input 3

5 5 7
0 0 2 4
2 3 4 5
3 5 5 2
5 5 5 4
0 3 5 1
2 2 4 4
0 5 4 1

Sample Output 3

YES

Sample Input 4

1 1 2
0 0 1 1
1 0 0 1

Sample Output 4

NO



Sample input:
4 2 3
0 1 3 1
1 1 4 1
2 0 2 2


Sample output:
YES

Submission status: Wrong Answer

Solution code:
import sys

input=sys.stdin.readline

def check_intersection(ax, ay, bx, by, cx, cy, dx, dy):
    dax, day = ax - bx, ay - by
    dcx, dcy = cx - dx, cy - dy
    ta = dcx * (ay - cy) + dcy * (cx - ax)
    tb = dcx * (by - cy) + dcy * (cx - bx)
    tc = dax * (cy - ay) + day * (ax - cx)
    td = dax * (dy - ay) + day * (ax - dx)
    return tc * td < 0 and ta * tb < 0

R,C,N=map(int,input().split())

def is_on_edge(x,y):
    return x==0 or x==R or y==0 or y==C

line=[]
for i in range(0,N):
    x1,y1,x2,y2=map(int,input().split())
    if is_on_edge(x1,y1) and is_on_edge(x2,y2):
        line.append([x1,y1,x2,y2])

def condition(R,C,line):
    n=len(line)
    def is_on_xaxis(x,y):
        return y==0 or y==C

    def is_on_yaxis(x,y):
        return x==0 or x==R

    xaxis=True
    for i in range(0,n):
        x1,y1,x2,y2=line[i]
        if (not is_on_xaxis(x1,y1) ) and (not is_on_xaxis(x2,y2)):
            xaxis=False
            break

    yaxis=True
    for i in range(0,n):
        x1,y1,x2,y2=line[i]
        if (not is_on_yaxis(x1,y1) ) and (not is_on_yaxis(x2,y2)):
            yaxis=False
            break

    if xaxis:
        X={0:[],C:[]}
        for i in range(0,n):
            x1,y1,x2,y2=line[i]
            if y1==0:
                if y2!=0:
                    X[0].append(line[i])
                else:
                    if x1>x2:
                        X[0].append([x2,y2,x1,y1])
            else:
                if y2!=C:
                    X[C].append(line[i])
                else:
                    if x1>x2:
                        X[C].append([x2,y2,x1,y1])

        m=len(X[0])
        k=len(X[C])
        X[0].sort()
        X[C].sort()
        for i in range(0,m-1):
            x1,y1,x2,y2=X[0][i]
            x3,y3,x4,y4=X[0][i+1]
            if check_intersection(x1,y1,x2,y2,x3,y3,x4,y4):
                print("NO")
                exit()
            else:
                if y1==y2:
                    if x2>=x3>=x1:
                        print("NO")
                        exit()

        for i in range(0,k-1):
            x1,y1,x2,y2=X[C][i]
            x3,y3,x4,y4=X[C][i+1]
            if check_intersection(x1,y1,x2,y2,x3,y3,x4,y4):
                print("NO")
                exit()
            else:
                if y1==y2:
                    if x2>=x3>=x1:
                        print("NO")
                        exit()
        if X[C]:
            for i in range(0,m):
                x1,y1,x2,y2=X[0][i]
                if y2==C:
                    start=0
                    end=k-1
                    while end-start>1:
                        test=(end+start)//2
                        if X[C][test][0]>=x2:
                            end=test
                        else:
                            start=test

                    if X[C][start][0]>=x2:
                        index=start
                    else:
                        if X[C][end][0]>=x2:
                            index=end
                        else:
                            index=k
                    #index-1,indexのやつと交差判定
                    if index!=0:
                        x3,y3,x4,y4=X[C][index-1]
                        if check_intersection(x1,y1,x2,y2,x3,y3,x4,y4):
                            print("NO")
                            exit()
                        else:
                            if y3==y4:
                                if x4>=x3>=x2:
                                    print("NO")
                                    exit()
                    if index!=k:
                        x3,y3,x4,y4=X[C][index]
                        if check_intersection(x1,y1,x2,y2,x3,y3,x4,y4):
                            print("NO")
                            exit()
                        else:
                            if y3==y4:
                                if x4>=x3>=x2:
                                    print("NO")
                                    exit()

        if X[0]:
            for i in range(0,k):
                x1,y1,x2,y2=X[C][i]
                if y2==0:
                    start=0
                    end=m-1
                    while end-start>1:
                        test=(end+start)//2
                        if X[0][test][0]>=x2:
                            end=test
                        else:
                            start=test

                    if X[0][start][0]>=x2:
                        index=start
                    else:
                        if X[0][end][0]>=x2:
                            index=end
                        else:
                            index=m
                    #index-1,indexのやつと交差判定
                    if index!=0:
                        x3,y3,x4,y4=X[0][index-1]
                        if check_intersection(x1,y1,x2,y2,x3,y3,x4,y4):
                            print("NO")
                            exit()
                        else:
                            if y3==y4:
                                if x4>=x3>=x2:
                                    print("NO")
                                    exit()
                    if index!=m:
                        x3,y3,x4,y4=X[0][index]
                        if check_intersection(x1,y1,x2,y2,x3,y3,x4,y4):
                            print("NO")
                            exit()
                        else:
                            if y3==y4:
                                if x4>=x3>=x2:
                                    print("NO")
                                    exit()
        print("YES")

    elif yaxis:
        r=R
        c=C
        C=r
        R=c
        for i in range(0,n):
            x1,y1,x2,y2=line[i]
            line[i]=[y1,x1,y2,x2]
        condition(R,C,line)
    else:
        print("NO")
        exit()

condition(R,C,line)

Submission status: Wrong Answer

Solution code:
class BIT():
    """区間加算、一点取得クエリをそれぞれO(logN)で答える
    add: 区間[l, r)にvalを加える
    get_val: i番目の値を求める
    i, l, rは0-indexed
    """
    def __init__(self, n):
        self.n = n
        self.bit = [0] * (n + 1)

    def _add(self, i, val):
        while i > 0:
            self.bit[i] += val
            i -= i & -i

    def get_val(self, i):
        """i番目の値を求める"""
        i = i + 1
        s = 0
        while i <= self.n:
            s += self.bit[i]
            i += i & -i
        return s

    def add(self, l, r, val):
        """区間[l, r)にvalを加える"""
        self._add(r, val)
        self._add(l, -val)


from operator import itemgetter


def compress(array):
    """座標圧縮したリストを返す"""
    set_ = set()
    for num in array:
        set_.add(num[0])
        set_.add(num[1])
    array2 = sorted(set_)
    memo = {value: index for index, value in enumerate(array2)}
    for i in range(len(array)):
        array[i] = (memo[array[i][0]], memo[array[i][1]])
    return array

def on_line(x, y):
    return x == 0 or x == c or y == 0 or y == r

def val(x, y):
    if y == 0:
        return x
    if x == r:
        return r + y
    if y == c:
        return r + c + (r - x)
    if x == 0:
        return r + c + r + (c - y)

r, c, n = map(int, input().split())
info = [list(map(int, input().split())) for i in range(n)]

res = []
for i in range(n):
    x1, y1, x2, y2 = info[i]
    if on_line(x1, y1) and on_line(x2, y2):
        left = val(x1, y1)
        right = val(x2, y2)
        if left > right:
            left, right = right, left
        res.append((left, right))


res = sorted(res, key=itemgetter(1))
res = compress(res)

bit = BIT(2 * len(res))
for left, right in res:
    if bit.get_val(left) != 0:
        print("NO")
        exit()
    else:
        bit.add(left, right + 1, 1)
print("YES")

Submission status: Wrong Answer

Solution code:
R,C,N=map(int,input().split())
d={}
for i in range(N):
	x1,y1,x2,y2=map(int,input().split())
	if x1==0 or x1==C or y1==0 or y1==R:
		if x2==0 or x2==C or y2==0 or y2==R:
			d[(x1,y1)]=i+1
			d[(x2,y2)]=i+1
d1={}
l=[]
for i in d:
	if i[0] not in d1:
		d1[i[0]]=[]
	d1[i[0]].append(i[1])
	l.append(i[0])
l1=[]
l.sort()
if len(l)==0:
	print("YES")
	exit()
for i in range(len(l)):
	if i>0:
		if l[i]==l[i-1]:
			continue
	if l[i]==0:
		d1[l[i]].sort()
	if l[i]==C:
		d1[l[i]].sort()
		d1[l[i]].reverse()
	for j in d1[l[i]]:
		if j>=R/2:
			c=d[(l[i],j)]
			if len(l1)>0:
				if l1[len(l1)-1]==c:
					del(l1[len(l1)-1])
				else:
					l1.append(c)
			else:
				l1.append(c)
l.reverse()
for i in range(len(l)):
	if i>0:
		if l[i]==l[i-1]:
			continue
	if l[i]==0:
		d1[l[i]].sort()
	if l[i]==C:
		d1[l[i]].sort()
		d1[l[i]].reverse()
	for j in d1[l[i]]:
		if j<R/2:
			c=d[(l[i],j)]
			if len(l1)>0:
				if l1[len(l1)-1]==c:
					del(l1[len(l1)-1])
				else:
					l1.append(c)
			else:
				l1.append(c)
if len(l1)>0:
	print("NO")
else:
	print("YES")

Submission status: Wrong Answer

Solution code:
R,C,N=map(int,input().split())
d={}
for i in range(N):
	x1,y1,x2,y2=map(int,input().split())
	if x1==0 or x1==C or y1==0 or y1==R:
		if x2==0 or x2==C or y2==0 or y2==R:
			d[(x1,y1)]=i+1
			d[(x2,y2)]=i+1
d1={}
l=[]
for i in d:
	if i[0] not in d1:
		d1[i[0]]=[]
	d1[i[0]].append(i[1])
	l.append(i[0])
l1=[]
l.sort()
if len(l)==0:
	print("YES")
	exit()
for i in range(len(l)):
	if l[i]==l[i-1]:
		continue
	if l[i]==0:
		d1[l[i]].sort()
	if l[i]==C:
		d1[l[i]].sort()
		d1[l[i]].reverse()
	for j in d1[l[i]]:
		if j>=R/2:
			c=d[(l[i],j)]
			if len(l1)>0:
				if l1[len(l1)-1]==c:
					del(l1[len(l1)-1])
				else:
					l1.append(c)
			else:
				l1.append(c)
l.reverse()
for i in range(len(l)):
	if l[i]==l[i-1]:
		continue
	if l[i]==0:
		d1[l[i]].sort()
	if l[i]==C:
		d1[l[i]].sort()
		d1[l[i]].reverse()
	for j in d1[l[i]]:
		if j<R/2:
			c=d[(l[i],j)]
			if len(l1)>0:
				if l1[len(l1)-1]==c:
					del(l1[len(l1)-1])
				else:
					l1.append(c)
			else:
				l1.append(c)
if len(l1)>0:
	print("NO")
else:
	print("YES")

Submission status: Wrong Answer

Solution code:
r,c,n = map(int,input().split())
xy = [list(map(int,input().split())) for i in range(n)]
ls = []
for x1,y1,x2,y2 in xy:
  if (x1 in (0,r) or y1 in (0,c)) and (x2 in (0,r) or y2 in (0,c)):
    k = []
    for x,y in ((x1,y1),(x2,y2)):
      if x == 0:
        s = 2*r+2*c-y
      if x == r:
        s = r+y
      if y == 0:
        s = x
      if y == c:
        s = 2*r+c-x
      k.append(s)
    t = len(ls)//2+1
    ls.append((k[0],t))
    ls.append((k[1],t))
if not ls:
  print("YES")
  exit()
ls.sort()
lsi = list(map(list,zip(*ls)))[1]
m = len(lsi)
seeing = [0 for i in range(m//2+1)]
seen = [0 for i in range(m//2+1)]
for i in range(1,m):
  r = lsi[i]
  q = lsi[i-1]
  if r == q:
    seeing[seen[q]] = 0
    seen[q] = 0
    continue
  if seen[r] == 0:
    seen[r] = q
    seeing[q] = r
  else:
    seeing[seen[r]] = 0
    seen[r] = 0
  if seeing[r] != 0:
    print("NO")
    exit()
print("YES")

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
from operator import itemgetter

X, Y, N = map(int, input().split())
U = []
D = []
R = []
L = []

def mustconsider(x, y):
    return (x in [0, X]) or (y in [0, Y])

def divide(x, y, i):
    if x == 0 and y != Y:
        L.append((y, i))
    if x == X and y != 0:
        R.append((y, i))
    if y == 0 and x != 0:
        D.append((x, i))
    if y == Y and x != X:
        U.append((x, i))

for i in range(N):
    x1, y1, x2, y2 = map(int, input().split())
    if mustconsider(x1, y1) and mustconsider(x2, y2):
        divide(x1, y1, i)
        divide(x2, y2, i)

D.sort()
R.sort()
U.sort(reverse=True)
L.sort(reverse=True)

Arounds = []
for _, ind in D:
    Arounds.append(ind)
for _, ind in R:
    Arounds.append(ind)
for _, ind in U:
    Arounds.append(ind)
for _, ind in L:
    Arounds.append(ind)


Ps = []
List = []
pre = -1
for a in Arounds:
    if a == pre:
        Ps.append(List)
        List = [a]
    else:
        List.append(a)
    pre = a
Ps.append(List)

ok = True
if len(Ps) == 2:
    P1, P2 = Ps
    if len(P1) != len(P2):
        ok = False
    else:
        n = len(P1)
        for i in range(n):
            if P1[i] != P2[n-1-i]:
                ok = False
                break
elif len(Ps) == 3:
    P1, P2, P3 = Ps
    P4 = P3 + P1
    if len(P4) != len(P2):
        ok = False
    else:
        n = len(P2)
        for i in range(n):
            if P2[i] != P4[n-1-i]:
                ok = False
                break
elif len(Ps) == 1:
    if not Ps[0]:
        ok = True
    else:
        ok = False
else:
    ok = False

print("YES" if ok else "NO")

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
from operator import itemgetter

X, Y, N = map(int, input().split())
U = []
D = []
R = []
L = []

def mustconsider(x, y):
    return (x in [0, X]) or (y in [0, Y])

def divide(x, y, i):
    if x == 0 and y != Y:
        L.append((y, i))
    if x == X and y != 0:
        R.append((y, i))
    if y == 0 and x != 0:
        D.append((x, i))
    if y == Y and x != X:
        U.append((x, i))

for i in range(N):
    x1, y1, x2, y2 = map(int, input().split())
    if mustconsider(x1, y1) and mustconsider(x2, y2):
        divide(x1, y1, i)
        divide(x2, y2, i)

D.sort()
R.sort()
U.sort(reverse=True)
L.sort(reverse=True)

Arounds = []
for _, ind in D:
    Arounds.append(ind)
for _, ind in R:
    Arounds.append(ind)
for _, ind in U:
    Arounds.append(ind)
for _, ind in L:
    Arounds.append(ind)


Ps = []
List = []
pre = -1
for a in Arounds:
    if a == pre:
        Ps.append(List)
        List = [a]
    else:
        List.append(a)
    pre = a
Ps.append(List)

ok = True
if len(Ps) == 2:
    P1, P2 = Ps
    if len(P1) != len(P2):
        ok = False
    else:
        n = len(P1)
        for i in range(n):
            if P1[i] != P2[n-1-i]:
                ok = False
                break
elif len(Ps) == 3:
    P1, P2, P3 = Ps
    P4 = P3 + P1
    if len(P4) != len(P2):
        ok = False
    else:
        n = len(P2)
        for i in range(n):
            if P2[i] != P4[n-1-i]:
                ok = False
                break
else:
    ok = False

print("YES" if ok else "NO")

Submission status: Wrong Answer

Solution code:
import random
import sys
input = sys.stdin.readline


class BIT():
    """区間加算、一点取得クエリをそれぞれO(logN)で答える
    add: 区間[l, r)にvalを加える
    get_val: i番目の値を求める
    i, l, rは0-indexed
    """
    def __init__(self, n):
        self.n = n
        self.bit = [0] * (n + 1)

    def _add(self, i, val):
        while i > 0:
            self.bit[i] += val
            i -= i & -i

    def get_val(self, i):
        """i番目の値を求める"""
        i = i + 1
        s = 0
        while i <= self.n:
            s += self.bit[i]
            i += i & -i
        return s

    def add(self, l, r, val):
        """区間[l, r)にvalを加える"""
        self._add(r, val)
        self._add(l, -val)


r, c, n = map(int, input().split())
info = [list(map(int, input().split())) for i in range(n)]

def solve(x1, y1):
    if y1 == 0:
        return x1
    if x1 == r:
        return r + y1
    if y1 == c:
        return r + c + (r-x1)
    if x1 == 0:
        return r + c + r + (c-y1)

def compress(array):
    set_ = set([])
    for i in range(len(array)):
        a, b = array[i]
        set_.add(a)
        set_.add(b)
    memo = {value : index for index, value in enumerate(sorted(list(set_)))}
    max_ = 0
    for i in range(len(array)):
        array[i][0] = memo[array[i][0]]
        array[i][1] = memo[array[i][1]]
        max_ = max(max_, *array[i])
    return max_, array

query = []
for i in range(n):
    x1, y1, x2, y2 = info[i]
    if (x1 % r == 0 or y1 % c == 0) and (x2 % r == 0 or y2 % c == 0):
        pos1, pos2 = solve(x1, y1), solve(x2, y2)
        if pos1 > pos2:
            pos1, pos2 = pos2, pos1
        query.append([pos1, pos2 + 1])

m, query = compress(query)
bit = BIT(m)  
for i in range(len(query)):
    begin, end = query[i]
    if bit.get_val(begin) != bit.get_val(end - 1):
        print("NO")
        exit()
    tmp = random.random()
    bit.add(begin, end, tmp)
print("YES")

Submission status: Wrong Answer

Solution code:
import collections

h, w, n = [ int(v) for v in input().split() ]
l = 2*h*w

def check(p1,p2,c3,c4):
    return p1 in [0,c3] or p2 in [0,c4]

def online(p1,p2,c3,c4):
    if p1 == 0:
        return p2
    elif p2 == 0:
        return 2*(c3+c4) - p1
    elif p1 == c3:
        return c3 + 2*c4 - p2
    elif p2 == c4:
        return c3 + p1

online_list = []
index = 0

for i in range(n):
    r1, c1, r2, c2 = [ int(v) for v in input().split() ]
    if check(r1,c1,h,w) and check(r2,c2,h,w):
        online_list.append((online(r1,c1,h,w),index))
        online_list.append((online(r2,c2,h,w),index))
        index += 1

online_list = [ i[1] for i in sorted(online_list) ]

ans = "NO"

dq = collections.deque([10**6])
for i in online_list:
    if dq[-1] == i:
        dq.pop()
    else:
        dq.append(i)

if len(dq) == 1:
    ans = "YES"

print(ans)

Submission status: Wrong Answer

Solution code:
import collections

h, w, n = [ int(v) for v in input().split() ]
l = 2*h*w

def check(p1,p2,c3,c4):
    return p1 in [0,c3] or p2 in [0,c4]

def online(p1,p2,c3,c4):
    if p1 == 0:
        return p2
    elif p2 == 0:
        return 2*(c3+c4) - p1
    elif p1 == c3:
        return c3 + 2*c4 - p2
    elif p2 == c4:
        return c3 + p2

online_list = []
index = 0

for i in range(n):
    r1, c1, r2, c2 = [ int(v) for v in input().split() ]
    if check(r1,c1,h,w) and check(r2,c2,h,w):
        online_list.append((online(r1,c1,h,w),index))
        online_list.append((online(r2,c2,h,w),index))
        index += 1

online_list = [ i[1] for i in sorted(online_list) ]

ans = "NO"

dq = collections.deque([10**6])
for i in online_list:
    if dq[-1] == i:
        dq.pop()
    else:
        dq.append(i)

if len(dq) == 1:
    ans = "YES"

print(ans)

Submission status: Wrong Answer

Solution code:
h, w, n = [ int(v) for v in input().split() ]
l = 2*h*w

def check(p1,p2,c3,c4):
    return p1 in [0,c3] or p2 in [0,c4]

def online(p1,p2,c3,c4):
    if p1 == 0:
        return p2
    elif p2 == 0:
        return 2*(c3+c4) - p1
    elif p1 == c3:
        return c3 + 2*c4 - p2
    elif p2 == c4:
        return c3 + p2

online_list = []
index = 0

for i in range(n):
    r1, c1, r2, c2 = [ int(v) for v in input().split() ]
    if check(r1,c1,h,w) and check(r2,c2,h,w):
        online_list.append((online(r1,c1,h,w),index))
        online_list.append((online(r2,c2,h,w),index))
        index += 1

online_list = [ i[1] for i in sorted(online_list) ]

ans = "NO"
ln = len(online_list) // 2
if online_list[0] == online_list[-1]:

    if online_list == online_list[::-1]:
        ans = "YES"
else:
    a, b = online_list[0], online_list[-1]
    for i in range(ln*2):
        if online_list[i] == a and i != 0:
            a_index = i
        if online_list[i] == b and i != ln*2-1:
            b_index = i
    if a_index % 2 == 1 and a_index + 1 == b_index:
        online_list_a = online_list[:b_index]
        online_list_b = online_list[b_index:]
        if online_list_a == online_list_a[::-1] and online_list_b == online_list_b[::-1]:
            ans = "YES"

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.buffer.readline
R, C, N = map(int, input().split())


def check(x, y):
    if x == 0:
        return y
    elif x == R:
        return R + C + C - y
    elif y == 0:
        return C + R + C + R - x
    elif y == C:
        return C + x
    else:
        return -1


lr_list = []
for _ in range(N):
    x1, y1, x2, y2 = map(int, input().split())
    z1, z2 = check(x1, y1), check(x2, y2)
    if z1 >= 0 and z2 >= 0:
        lr_list.append((min(z1, z2), max(z1, z2)))

lr_list.sort(key=lambda p: p[0])
ok = 1
for i in range(1, len(lr_list)):
    if lr_list[i][1] > lr_list[i-1][1]:
        ok = 0
        break

if lr_list[-1][0] > lr_list[0][1]:
    ok = 0

if ok:
    print('YES')
else:
    print('NO')

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.buffer.readline
R, C, N = map(int, input().split())


def check(x, y):
    if x == 0:
        return y
    elif x == R:
        return R + C + C - y
    elif y == 0:
        return C + R + C + R - x
    elif y == C:
        return C + x
    else:
        return -1


lr_list = []
for _ in range(N):
    x1, y1, x2, y2 = map(int, input().split())
    z1, z2 = check(x1, y1), check(x2, y2)
    if z1 >= 0 and z2 >= 0:
        lr_list.append((min(z1, z2), max(z1, z2)))

lr_list.sort(key=lambda p: p[0])
ok = 1
for i in range(1, len(lr_list)):
    if lr_list[i][1] > lr_list[i-1][1]:
        ok = 0
        break
if ok:
    print('YES')
else:
    print('NO')

Submission status: Wrong Answer

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    
    R,C,N = map(int,input().split())
    P = []
    X = {0,R}
    Y = {0,C}
    M = 0
    for i in range(N):
        x1,y1,x2,y2 = map(int,input().split())
        if (x1 in X or y1 in Y) and  (x2 in X or y2 in Y):
            if y1==0:
                L1 = x1
            elif x1==R:
                L1 = R+y1
            elif y1==C:
                L1 = 2*R + C - x1
            else:
                L1 = 2*(R+C) - y1
            
            if y2==0:
                L2 = x2
            elif x2==R:
                L2 = R+y2
            elif y2==C:
                L2 = 2*R + C - x2
            else:
                L2 = 2*(R+C) - y2
                
            P.append([min(L1,L2), max(L1,L2)])
    P = sorted(P, key = lambda a:a[0])
    M = len(P)
    print("AAA")
    sys.exit()
    
    flag = 0
    Q = []
    for i in range(M):
        x1,x2 = P[i]
        if Q == []:
            Q.append([x1,x2])
        else:
            while Q[-1][1] < x1 and Q!=[]:
                Q.pop()
            if Q==[]:
                Q.append([x1,x2])
            else:
                y1,y2 = Q[-1]
                if y2 < x2:
                    flag = 1
                    break
                else:
                    Q.append([x1,x2])
    if flag == 1:
        print("NO")
    else:
        print("YES")
    
main()

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline

def main():
    R, C, N = map(int, input().split())
    xyxy = [list(map(int, input().split())) for i in range(N)]

    r = []

    for i in range(N):
        x1, y1, x2, y2 = xyxy[i]
        # どちらも周上にある場合は周上の座標に変換してから記録
        if ((x1 == 0 or x1 == R) or (y1 == 0 or y1 == C)) and ((x2 == 0 or x2 == R) or (y2 == 0 or y2 == C)):
            # １つ目
            if x1 == 0:
                r.append((y1, i))
            elif x1 == R:
                r.append((C - y1 + C + R, i))
            elif y1 == 0:
                r.append((R - x1 + C * 2 + R, i))
            else:
                r.append((x1 + C, i))
            # 2つ目
            if x2 == 0:
                r.append((y2, i))
            elif x2 == R:
                r.append((C - y2 + C + R, i))
            elif y2 == 0:
                r.append((R - x2 + C * 2 + R, i))
            else:
                r.append((x2 + C, i))
    
    r = sorted(r)
    stack = []
    for i in range(len(r)):
        if len(stack) > 0:
            if stack[-1] == r[i]:
                stack.pop()
            else:
                stack.append(r[i])
        else:
            stack.append(r[i])
    
    if len(stack) > 0:
        print("NO")
    else:
        print("YES")
            



if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline

def main():
    R, C, N = map(int, input().split())
    xyxy = [list(map(int, input().split())) for i in range(N)]

    r = []

    for i in range(N):
        x1, y1, x2, y2 = xyxy[i]
        # どちらも周上にある場合は周上の座標に変換してから記録
        if ((x1 == 0 or x1 == R) and (y1 == 0 or y2 == C)) and ((x2 == 0 or x2 == R) and (y2 == 0 or y2 == C)):
            # １つ目
            if x1 == 0:
                r.append((y1, i))
            elif x1 == R:
                r.append((C - y1 + C + R, i))
            elif y1 == 0:
                r.append((R - x1 + C * 2 + R, i))
            else:
                r.append((x1 + C, i))
            # 2つ目
            if x2 == 0:
                r.append((y2, i))
            elif x2 == R:
                r.append((C - y2 + C + R, i))
            elif y2 == 0:
                r.append((R - x2 + C * 2 + R, i))
            else:
                r.append((x2 + C, i))
    
    r = sorted(r)
    stack = []
    for i in range(len(r)):
        if len(stack) > 0:
            if stack[-1] == r[i]:
                stack.pop()
            else:
                stack.append(r[i])
        else:
            stack.append(r[i])
    
    if len(stack) > 0:
        print("NO")
    else:
        print("YES")
            



if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
import math

"""
内部の点が絡むものは、曲線で結んでホモトピーで変形すれば、無視できる
境界の2点を結ぶものたちだけが問題
"""

R,C,N = map(int,input().split())
pts = [] # 角度、番号
is_inner = lambda x,y:  0 < x < R and 0 < y < C
for i in range(N):
    x1,y1,x2,y2 = map(int,input().split())
    if is_inner(x1,y1) or is_inner(x2,y2):
        continue
    pts.append((math.atan2(y1,x1),i))
    pts.append((math.atan2(y2,x2),i))
pts.sort()

arr = []
for _, i in pts:
    if arr and arr[-1] == i:
        arr.pop()
        continue
    arr.append(i)

answer = 'NO' if arr else 'YES'
print(answer)

Submission status: Wrong Answer

Solution code:
import sys, math, collections, heapq, itertools
F = sys.stdin
def single_input(): return F.readline().strip("\n")
def line_input(): return F.readline().strip("\n").split()

def solve():
    R, C, N = map(int, line_input())
    u, l, r, d = [], [], [], []
    for i in range(N):
        x, y, z, w = map(int, line_input())
        if x == 0:
            if z == 0: 
                u.append((x, y, i))
                u.append((z, w, i))
            elif w == C:
                u.append((x, y, i))
                r.append((z, w, i))
            elif z == R:
                u.append((x, y, i))
                d.append((z, w, i))
            elif w == 0:
                u.append((x, y, i))
                l.append((x, y, i))
        elif x == R:
            if z == 0: 
                d.append((x, y, i))
                u.append((z, w, i))
            elif w == C:
                d.append((x, y, i))
                r.append((z, w, i))
            elif z == R:
                d.append((x, y, i))
                d.append((z, w, i))
            elif w == 0:
                d.append((x, y, i))
                l.append((x, y, i))
        elif y == 0:
            if z == 0: 
                l.append((x, y, i))
                u.append((z, w, i))
            elif w == C:
                l.append((x, y, i))
                r.append((z, w, i))
            elif z == R:
                l.append((x, y, i))
                d.append((z, w, i))
            elif w == 0:
                l.append((x, y, i))
                l.append((x, y, i))
        elif y == C:
            if z == 0: 
                r.append((x, y, i))
                u.append((z, w, i))
            elif w == C:
                r.append((x, y, i))
                r.append((z, w, i))
            elif z == R:
                r.append((x, y, i))
                d.append((z, w, i))
            elif w == 0:
                r.append((x, y, i))
                l.append((x, y, i))
    u.sort()
    r.sort()
    d.sort(reverse = True)
    l.sort(reverse = True)

    s = []
    used = set()
    crossed = True
    for point in u:
        if point[2] not in used:
            s.append(point[2])
            used |= {point[2]}
        else:
            if s[-1] != point[2]: break
            else: s.pop()
    else:
        for point in r:
            if point[2] not in used:
                s.append(point[2])
                used |= {point[2]}
            else:
                if s[-1] != point[2]: break
                else: s.pop()
        else:
            for point in d:
                if point[2] not in used:
                    s.append(point[2])
                    used |= {point[2]}
                else:
                    if s[-1] != point[2]: break
                    else: s.pop()
            else:
                for point in l:
                    if point[2] not in used:
                        s.append(point[2])
                        used |= {point[2]}
                    else:
                        if s[-1] != point[2]: break
                        else: s.pop()
                else: crossed = False

    print("NO" if crossed else "YES")
                            
    return 0
  
if __name__ == "__main__":
    solve()

Submission status: Wrong Answer

Solution code:
import sys, math, collections, heapq, itertools
F = sys.stdin
def single_input(): return F.readline().strip("\n")
def line_input(): return F.readline().strip("\n").split()
def gcd(a, b):
    a, b = max(a, b), min(a, b)
    while a % b > 0: a, b = b, a % b
    return b

def cross(ax, ay, bx, by, cx, cy, dx, dy): #axaybxbyとcxcydxdyが交差するかどうか
    crossed = True
    if ax >= bx:
        if ax < cx and ax < dx: crossed = False
        elif bx > cx and bx > dx: crossed = False
    else:
        if bx < cx and bx < dx: crossed = False
        elif ax > cx and ax > dx: crossed = False
    if not crossed: return crossed

    if ay >= by:
        if ay < cy and ay < dy: crossed = False
        elif by > cy and by > dy: crossed = False
    else:
        if by < cy and by < dy: crossed = False
        elif ay > cy and ay > dy: crossed = False
    if not crossed: return crossed

    if ((ax-bx)*(cy-ay)+(ay-by)*(ax-cx))*((ax-bx)*(dy-ay)+(ay-by)*(ax-dx)) > 0: crossed = False
    if ((cx-dx)*(ay-cy)+(cy-dy)*(cx-ax))*((cx-dx)*(by-cy)+(cy-dy)*(cx-bx)) > 0: crossed = False
    return crossed

  
def solve():
    R, C, N = map(int, line_input())
    L = []
    for i in range(N):
        x, y, a, b = map(int, line_input())
        if x == 0 or x == R:
            if a == 0 or a == R or b == 0 or b == C: L.append((x, y, a, b))
        elif y == 0 or y == C:
            if a == 0 or a == R or b == 0 or b == C: L.append((x, y, a, b))
    possible = True
    for i in range(len(L)):
        for j in range(i+1, len(L)):
            if cross(L[i][0], L[i][1], L[i][2], L[i][3], L[j][0], L[j][1], L[j][2], L[j][3]):
                print("NO")
                possible = False
                break
        if not possible: break
    else: print("YES")
        
    return 0
  
if __name__ == "__main__":
    solve()