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:
def f(x, y):
    if x == 0:
        return y
    if y == 0:
        return -x
    if x == r:
        return -(x + y)
    if y == c:
        return x + y

def print_no():
    print("NO")
    exit()

def print_yes():
    print("YES")
    exit()

r, c, n = map(int, input().split())
xy = []
lxy = 0
for i in range(n):
    x1, y1, x2, y2 = map(int, input().split())
    d = []
    if min(x1, y1) == 0 or x1 == r or y1 == c:
        d.append([f(x1, y1), i])
    if min(x2, y2) == 0 or x2 == r or y2 == c:
        d.append([f(x2, y2), i])
    if len(d) == 2:
        xy.append(d[0])
        xy.append(d[1])
        lxy += 2
if lxy == 0:
    print_yes()
xy.sort()
lxy0 = lxy // 2
if not xy[0][1] == xy[lxy - 1][1]:
    c1, c2 = -1, -1
    for i in range(lxy - 1):
        if xy[i][1] == xy[i + 1][1]:
            c1, c2 = i, i + lxy0
            break
    if c1 == c2 == -1 or c2 >= lxy - 1:
        print_no()
    if lxy == 2:
        print_yes()
    for j in range(c1 + 1):
        if not xy[c1 - j][1] == xy[c1 + 1 + j][1]:
            print_no()
    for j in range(lxy0 - (c1 + 1)):
        if not xy[c2 - j][1] == xy[c2 + 1 + j][1]:
            print_no()
else:
    for i in range(lxy0):
        j = lxy - i - 1
        if not xy[i][1] == xy[j][1]:
            print_no()
print_yes()

Submission status: Wrong Answer

Solution code:
def f(x, y):
    if x == 0:
        return y
    if y == 0:
        return -x
    if x == r:
        return -(x + y)
    if y == c:
        return x + y

def print_no():
    print("NO")
    exit()

def print_yes():
    print("YES")
    exit()

r, c, n = map(int, input().split())
xy = []
lxy = 0
for i in range(n):
    x1, y1, x2, y2 = map(int, input().split())
    d = []
    if min(x1, y1) == 0 or x1 == r or y1 == c:
        d.append([f(x1, y1), i])
    if min(x2, y2) == 0 or x2 == r or y2 == c:
        d.append([f(x2, y2), i])
    if len(d) == 2:
        xy.append(d[0])
        xy.append(d[1])
        lxy += 2
if not xy:
    print_yes()
xy.sort()
s = 114514
ap = [0] * (n + 5)
t = 0
if not xy[0][1] == xy[lxy - 1][1]:
    for i in range(lxy):
        if t == 0:
            if ap[xy[i][1]] == 0:
                ap[xy[i][1]] = s
                s += 1
            elif xy[i][1] == xy[i - 1][1]:
                ap[xy[i][1]] = ap[xy[i - 1][1]]
                s -= 2
                t = 1
                u = 3
            else:
                print_no()
        elif t == 1:
            if xy[i][1] == xy[i - u][1]:
                s -= 1
                u += 2
            else:
                print_no()
            if s < 114514:
                t = 2
        elif t == 2:
            if ap[xy[i][1]] == 0:
                ap[xy[i][1]] = s
                s -= 1
            elif xy[i][1] == xy[i - 1][1]:
                ap[xy[i][1]] = ap[xy[i - 1][1]]
                s += 2
                t = 3
                u = 3
            else:
                print_no()
        elif t == 3:
            if xy[i][1] == xy[i - u][1]:
                s += 1
                u += 2
            else:
                print_no()
            if s > 114514:
                t = 4
        else:
            break
else:
    for i in range(lxy // 2):
        j = lxy - i - 1
        if not xy[i][1] == xy[j][1]:
            print_no()
print_yes()

Submission status: Wrong Answer

Solution code:
import cmath
r, c, n = map(int, input().split())
lis = []
for i in range(n):
    x1, y1, x2, y2 = map(int, input().split())
    if 0 < x1 < r and 0 < x2 < r and 0 < y1 < c and 0 < y2 < c:
        continue
    else:
        lis.append((i, x1 - r / 2 + (y1 - c / 2) * 1j))
        lis.append((i, x2 - r / 2 + (y2 - c / 2) * 1j))
lis.sort(key=lambda x: cmath.phase(x[1]))
stack = []
for i in lis:
    if stack == [] or stack[-1] != i[0]:
        stack.append(i[0])
    else:
        stack.pop()
if stack == []:
    print("YES")
else:
    print("NO")

Submission status: Wrong Answer

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

r,c,n = map(int,readline().split())
data = list(map(int,read().split()))
p = []
for i in range(n):
    x1,y1,x2,y2 = data[i*4:i*4+4]
    if((x1==0)|(x1==r)|(y1==0)|(x1==c))&((x2==0)|(x2==r)|(y2==0)|(y2==c)):
        for x,y in zip([x1,x2],[y1,y2]):
            num = 0
            if(x==0):
                num = y
            elif(x==r):
                num = r+2*c-y
            elif(y==0):
                num = 2*(r+c)-x
            else:
                num = c+x
            p.append([num,i])

p.sort()
d = []
for _,i in p:
    if(not d):
        d.append(i)
    else:
        right = d.pop()
        if(right != i):
            d.append(right)
            d.append(i)

if(len(d)==0):
    print('YES')
else:
    print('NO')

Submission status: Wrong Answer

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

r,c,n = map(int,readline().split())
data = list(map(int,read().split()))
p = []
for i in range(n):
    x1,y1,x2,y2 = data[i*4:i*4+4]
    if((x1==0)|(x1==r)|(y1==0)|(x1==c))&((x2==0)|(x2==r)|(y2==0)|(y2==c)):
        for x,y in zip([x1,x2],[y1,y2]):
            num = 0
            if(x==0):
                num = y
            elif(x==r):
                num = r+2*c-y
            elif(y==0):
                num = 2*(r+c)-x
            else:
                num = c+x
            p.append([num,i])

p.sort()
p_len = len(p)
for i in range(p_len):
    left = (i-1)%p_len
    right = (i+1)%p_len

    if(p[i][1] != p[left][1])&(p[i][1] != p[right][1]):
        print('NO')
        exit()

print('YES')

Submission status: Wrong Answer

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

def conv(i, j):
  res = 0
  if i == 0:
    res = j
  elif j == C:
    res = C + i
  elif i == R:
    res = C + R + (C - j)
  elif j == 0: res = 2 * C + R + (R - j)
  else: res = -1
  return res

for i in range(N):
  x, y, u, v = map(int, input().split())
  d, dd = conv(x, y), conv(u, v)
  if d >= 0 and (dd >= 0):
    a.append((d, i))
    a.append((dd, i))
a.sort()
s = []
for _, i in a:
  if len(s) and s[-1] == i: s.pop()
  else: s.append(i)
if len(s): print("NO")
else: print("YES")

Submission status: Wrong Answer

Solution code:
r, c, n = map(int, input().split())
l = []
for i in range(n):
    x1, y1, x2, y2 = map(int, input().split())
    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:
            l.append((y1, i))
        elif y1 == c:
            l.append((c + x1, i))
        elif x1 == r:
            l.append((c * 2 + r - y1, i))
        else:
            l.append((r * 2 + c * 2 - x1, i))
        if x2 == 0:
            l.append((y2, i))
        elif y2 == c:
            l.append((c + x2, i))
        elif x2 == r:
            l.append((c * 2 + r - y2, i))
        else:
            l.append((r * 2 + c * 2 - x2, i))
l.sort()
s = [l[0][1]]
for x, i in l[1:]:
    s.append(0)
    s.append(i)
r = [0] * len(s)
i, j = 0, 0
while i < len(s):
    while i - j >= 0 and i + j < len(s) and s[i - j] == s[i + j]:
        j += 1
    r[i] = j
    k = 1
    while i - k >= 0 and k + r[i - k] < j:
        r[i + k] = r[i - k]
        k += 1
    i += k
    j -= k
for i in range(1, len(s), 2):
    p = r[i]
    if i == p - 1:
        m = (len(s) - p * 2) // 2
        if m == -1 or (m > 0 and r[-m] == m):
            print('YES')
            exit(0)
print('NO')

Submission status: Wrong Answer

Solution code:
r, c, n = map(int, input().split())
l = []
for i in range(n):
    x1, y1, x2, y2 = map(int, input().split())
    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:
            l.append((y1, i))
        elif y1 == c:
            l.append((r + x1, i))
        elif x1 == r:
            l.append((r * 2 + c - y1, i))
        else:
            l.append((r * 2 + c * 2 - x1, i))
        if x2 == 0:
            l.append((y2, i))
        elif y2 == c:
            l.append((r + x2, i))
        elif x2 == r:
            l.append((r * 2 + c - y2, i))
        else:
            l.append((r * 2 + c * 2 - x2, i))
l.sort()
s = [l[0][1]]
for x, i in l[1:]:
    s.append(0)
    s.append(i)
r = [0] * len(s)
i, j = 0, 0
while i < len(s):
    while i - j >= 0 and i + j < len(s) and s[i - j] == s[i + j]:
        j += 1
    r[i] = j
    k = 1
    while i - k >= 0 and k + r[i - k] < j:
        r[i + k] = r[i - k]
        k += 1
    i += k
    j -= k
for i in range(1, len(s), 2):
    p = r[i]
    if i == p - 1:
        m = (len(s) - p * 2) // 2
        if m == -1 or (m > 0 and r[-m] == m):
            print('YES')
            exit(0)
print('NO')

Submission status: Wrong Answer

Solution code:
def N(): return int(input())
def NM():return map(int,input().split())
def L():return list(NM())
def LN(n):return [N() for i in range(n)]
def LL(n):return [L() for i in range(n)]
r,c,n=NM()
x=[]
y=[]
def NO():
    print("NO")
    quit()
for i in range(n):
    x1,y1,x2,y2=NM()
    if x2<x1:
        x1,y1,x2,y2=x2,y2,x1,y1
    if x2-x1==r:
        if y:
            NO()
        x.append((y1,y2))
    elif abs(y2-y1)==c:
        if y2<y1:
            x1,y1,x2,y2=x2,y2,x1,y1
        if x:
            NO()
        y.append((x1,x2))
if x:
    x.sort()
    t=x[0][1]
    for x1,x2 in x:
        if t>x2:
            NO()
        t=x2
if y:
    y.sort()
    t=y[0][1]
    for y1,y2 in y:
        if t>y2:
            NO()
        t=y2
print("YES")

Submission status: Wrong Answer

Solution code:
def N(): return int(input())
def NM():return map(int,input().split())
def L():return list(NM())
def LN(n):return [N() for i in range(n)]
def LL(n):return [L() for i in range(n)]
r,c,n=NM()
x=[]
y=[]
def NO():
    print("NO")
    quit()
for i in range(n):
    x1,y1,x2,y2=NM()
    if abs(x2-x1)==r:
        if y:
            NO()
        x.append((x1,x2))
    elif abs(y2-y1)==c:
        if x:
            NO()
        y.append((y1,y2))
if x:
    x.sort()
    t=x[0][1]
    for x1,x2 in x:
        if t>x2:
            NO()
        t=x2
if y:
    y.sort()
    t=y[0][1]
    for y1,y2 in y:
        if t>y2:
            NO()
        t=y2
print("YES")

Submission status: Wrong Answer

Solution code:
R, C, N = map(int, input().split())
edge = []


def isEdge(x, y):
    if x == 0 and y == 0:
        return 1
    elif x == 0:
        return 1 + 2 * (R + C) - y
    elif x == R:
        return 1 + R + y
    elif y == 0:
        return 1 + x
    elif y == C:
        return 1 + R + 2 * C - x
    else:
        return False


for i in range(1, N + 1):
    x1, y1, x2, y2 = map(int, input().split())
    d1 = isEdge(x1, y1)
    d2 = isEdge(x2, y2)
    if d1 and d2:
        edge.append((d1, i))
        edge.append((d2, i))

edge.sort()
stack = []
used = [False] * (1 + N)

ans = "YES"
for _, x in edge:
    if not used[x]:
        used[x] = True
        stack.append(x)
    else:
        y = stack.pop()
        if x != y:
            ans = "NO"
            break

print(ans)

Submission status: Wrong Answer

Solution code:
R, C, N = map(int, input().split())
edge = []


def isEdge(x, y):
    if x == 0 and y == 0:
        return 1
    elif x == 0:
        return 1 + 2 * (R + C) - y
    elif x == R:
        return 1 + R + y
    elif y == 0:
        return 1 + x
    elif y == C:
        return 1 + R + 2 * C - x
    else:
        return False


for i in range(1, N + 1):
    x1, y1, x2, y2 = map(int, input().split())
    d1 = isEdge(x1, y1)
    d2 = isEdge(x2, y2)
    if d1 and d2:
        edge.append((d1, i))
        edge.append((d2, i))

edge.sort()
stack = []
for _, i in edge:
    if not stack:
        stack.append(i)
    elif i == stack[-1]:
        stack.pop()
    else:
        stack.append(i)

if stack:
    print("NO")
else:
    print("YES")

Submission status: Wrong Answer

Solution code:
w, h, n = map(int, input().split())

pos = []
for i in range(n):
    x1, y1, x2, y2 = map(int, input().split())
    if (x1 in [0, w] or y1 in [0, h]) and (x2 in [0, w] or y2 in [0, h]):
        pos.append((x1, y1, i))
        pos.append((x2, y2, i))

pos.sort(key=lambda v: v[0]) # top →
edge = [v[-1] for v in pos if v[1] == 0 and v[0] != 0]

pos.sort(key=lambda v: v[1]) # left ↓
edge += [v[-1] for v in pos if v[0] == w and v[1] != 0]

pos.sort(key=lambda v: v[0], reverse=True) # bottom ←
edge += [v[-1] for v in pos if v[1] == h and v[0] != w]

pos.sort(key=lambda v: v[0], reverse=True) # right ↑
edge += [v[-1] for v in pos if v[0] == 0 and v[1] != h]

for i in range(len(edge) - 1):
    if edge[i] == edge[i + 1]:
        break
for j in range(len(edge) // 2):
    if edge[(i + j + 1) % n] != edge[(i - j + n) % n]:
        print("NO")
        break
else:
    print("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])

n=len(line)
for i in range(0,n):
    x1,y1,x2,y2=line[i]
    if x2<x1:
        x1,x2=x2,x1
        y1,y2=y2,y1
    elif x2==x1:
        if y2<y1:
            y1,y2=y2,y1
    line[i]=[x1,y1,x2,y2]

line.sort()
height=[]
wide=[]
X={0:[],R:[]}
Y={0:[],C:[]}
for i in range(0,n):
    x1,y1,x2,y2=line[i]
    if x1==0:
        if x2==0:
            X[0].append(line[i])
        else:
            height.append(line[i])
    elif x1==R:
        X[R].append(line[i])
    else:
        if y1==0 and y2==0:
            Y[0].append(line[i])
        elif y1==C and y2==C:
            Y[C].append(line[i])
        else:
            wide.append(line[i])

height.sort()
wide.sort()
X[0].sort()
X[R].sort()
Y[0].sort()
Y[C].sort()
ans="YES"
for i in range(len(height)-1):
    x1,y1,x2,y2=height[i]
    x3,y3,x4,y4=height[i+1]
    if check_intersection(x1,y1,x2,y2,x3,y3,x4,y4):
        ans="NO"


for i in range(len(wide)-1):
    x1,y1,x2,y2=wide[i]
    x3,y3,x4,y4=wide[i+1]
    if check_intersection(x1,y1,x2,y2,x3,y3,x4,y4):
        ans="NO"

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

for i in range(len(X[R])-1):
    x1,y1,x2,y2=X[R][i]
    x3,y3,x4,y4=X[R][i+1]
    if y4>=y2>=y3>=y1:
        print("NO")
        exit()

for i in range(len(Y[0])-1):
    x1,y1,x2,y2=Y[0][i]
    x3,y3,x4,y4=Y[0][i+1]
    if x4>=x2>=x3>=x1:
        print("NO")
        exit()

for i in range(len(Y[C])-1):
    x1,y1,x2,y2=Y[C][i]
    x3,y3,x4,y4=Y[C][i+1]
    if x4>=x2>=x3>=x1:
        print("NO")
        exit()

if wide:
    for i in range(0,len(height)):
        x1,y1,x2,y2=height[i]
        x3,y3,x4,y4=wide[0]
        if check_intersection(x1,y1,x2,y2,x3,y3,x4,y4):
            ans="NO"

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

        if y1>=X[0][end][1]:
            index=end
        elif y1>=X[0][start][1]:
            index=start
        else:
            index=-1
        if index!=-1:
            x3,y3,x4,y4=X[0][index]
            if y4>=y1:
                ans="NO"

    if y2==0 and Y[0]:
        start=0
        end=len(Y[0])-1
        while end-start>1:
            test=(end+start)//2
            if x2>=Y[0][test][0]:
                start=test
            else:
                end=test

        if x2>=Y[0][end][0]:
            index=end
        elif x2>=Y[0][start][0]:
            index=start
        else:
            index=-1
        if index!=-1:
            x3,y3,x4,y4=Y[0][index]
            if x4>=x2:
                ans="NO"

    if y2==C and Y[C]:
        start=0
        end=len(Y[C])-1
        while end-start>1:
            test=(end+start)//2
            if x2>=Y[C][test][0]:
                start=test
            else:
                end=test

        if x2>=Y[C][end][0]:
            index=end
        elif x2>=Y[C][start][0]:
            index=start
        else:
            index=-1
        if index!=-1:
            x3,y3,x4,y4=Y[C][index]
            if x4>=x2:
                ans="NO"

    if x2==R and X[R]:
        start=0
        end=len(X[R])-1
        while end-start>1:
            test=(end+start)//2
            if y2>=X[R][test][1]:
                start=test
            else:
                end=test

        if y2>=X[R][end][1]:
            index=end
        elif y2>=X[R][start][1]:
            index=start
        else:
            index=-1
        if index!=-1:
            x3,y3,x4,y4=X[R][index]
            if y4>=y2:
                ans="NO"


for i in range(0,len(wide)):
    x1,y1,x2,y2=wide[i]
    if y1==0 and Y[0]:
        start=0
        end=len(Y[0])-1
        while end-start>1:
            test=(end+start)//2
            if x1>=Y[0][test][0]:
                start=test
            else:
                end=test

        if x1>=Y[0][end][0]:
            index=end
        elif x1>=Y[0][start][0]:
            index=start
        else:
            index=-1
        if index!=-1:
            x3,y3,x4,y4=Y[0][index]
            if x4>=x1:
                ans="NO"
                exit()

    if y2==0 and Y[0]:
        start=0
        end=len(Y[0])-1
        while end-start>1:
            test=(end+start)//2
            if x2>=Y[0][test][0]:
                start=test
            else:
                end=test

        if x2>=Y[0][end][0]:
            index=end
        elif x2>=Y[0][start][0]:
            index=start
        else:
            index=-1
        if index!=-1:
            x3,y3,x4,y4=Y[0][index]
            if x4>=x2:
                ans="NO"
                exit()

    if y2==C and Y[C]:
        start=0
        end=len(Y[C])-1
        while end-start>1:
            test=(end+start)//2
            if x2>=Y[C][test][0]:
                start=test
            else:
                end=test

        if x2>=Y[C][end][0]:
            index=end
        elif x2>=Y[C][start][0]:
            index=start
        else:
            index=-1
        if index!=-1:
            x3,y3,x4,y4=Y[C][index]
            if x4>=x2:
                ans="NO"

    if y1==C and Y[C]:
        start=0
        end=len(Y[C])-1
        while end-start>1:
            test=(end+start)//2
            if x1>=Y[C][test][0]:
                start=test
            else:
                end=test

        if x1>=Y[C][end][0]:
            index=end
        elif x1>=Y[C][start][0]:
            index=start
        else:
            index=-1
        if index!=-1:
            x3,y3,x4,y4=Y[C][index]
            if x4>=x1:
                ans="NO"

    if x2==R and X[R]:
        start=0
        end=len(X[R])-1
        while end-start>1:
            test=(end+start)//2
            if y2>=X[R][test][1]:
                start=test
            else:
                end=test

        if y2>=X[R][end][1]:
            index=end
        elif y2>=X[R][start][1]:
            index=start
        else:
            index=-1
        if index!=-1:
            x3,y3,x4,y4=X[R][index]
            if y4>=y2:
                ans="NO"

    if x1==R and X[R]:
        start=0
        end=len(X[R])-1
        while end-start>1:
            test=(end+start)//2
            if y1>=X[R][test][1]:
                start=test
            else:
                end=test

        if y1>=X[R][end][1]:
            index=end
        elif y1>=X[R][start][1]:
            index=start
        else:
            index=-1
        if index!=-1:
            x3,y3,x4,y4=X[R][index]
            if y4>=y1:
                ans="NO"


print(ans)

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=[]
node=set([])
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])
        node.add((x1,y1))
        node.add((x2,y2))

n=len(line)
for i in range(0,n):
    x1,y1,x2,y2=line[i]
    if x2<x1:
        x1,x2=x2,x1
        y1,y2=y2,y1
    elif x2==x1:
        if y2<y1:
            y1,y2=y2,y1
    line[i]=[x1,y1,x2,y2]

line.sort()
height=[]
wide=[]
X={0:[],R:[]}
Y={0:[],C:[]}
for i in range(0,n):
    x1,y1,x2,y2=line[i]
    if x1==0:
        if x2==0:
            X[0].append(line[i])
        else:
            height.append(line[i])
    elif x1==R:
        X[R].append(line[i])
    else:
        if y1==0 and y2==0:
            Y[0].append(line[i])
        elif y1==C and y2==C:
            Y[C].append(line[i])
        else:
            wide.append(line[i])

height.sort()
wide.sort()
X[0].sort()
X[R].sort()
Y[0].sort()
Y[C].sort()
ans="YES"
for i in range(len(height)-1):
    x1,y1,x2,y2=height[i]
    x3,y3,x4,y4=height[i+1]
    if check_intersection(x1,y1,x2,y2,x3,y3,x4,y4):
        ans="NO"


for i in range(len(wide)-1):
    x1,y1,x2,y2=wide[i]
    x3,y3,x4,y4=wide[i+1]
    if check_intersection(x1,y1,x2,y2,x3,y3,x4,y4):
        ans="NO"

if wide:
    for i in range(0,len(height)):
        x1,y1,x2,y2=height[i]
        x3,y3,x4,y4=wide[0]
        if check_intersection(x1,y1,x2,y2,x3,y3,x4,y4):
            ans="NO"


print(ans)

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=[]
node=set([])
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])
        node.add((x1,y1))
        node.add((x2,y2))

n=len(line)
for i in range(0,n):
    x1,y1,x2,y2=line[i]
    if x2<x1:
        x1,x2=x2,x1
        y1,y2=y2,y1
    elif x2==x1:
        if y2<y1:
            y1,y2=y2,y1
    line[i]=[x1,y1,x2,y2]

line.sort()
height=[]
wide=[]
X={0:[],R:[]}
Y={0:[],C:[]}
for i in range(0,n):
    x1,y1,x2,y2=line[i]
    if x1==0:
        if x2==0:
            X[0].append(line[i])
        else:
            height.append(line[i])
    elif x1==R:
        X[R].append(line[i])
    else:
        if y1==0 and y2==0:
            Y[0].append(line[i])
        elif y1==C and y2==C:
            Y[C].append(line[i])
        else:
            wide.append(line[i])

height.sort()
wide.sort()
X[0].sort()
X[R].sort()
Y[0].sort()
Y[C].sort()
ans="YES"
for i in range(len(height)-1):
    x1,y1,x2,y2=height[i]
    x3,y3,x4,y4=height[i+1]
    if check_intersection(x1,y1,x2,y2,x3,y3,x4,y4):
        ans="NO"


for i in range(len(wide)-1):
    x1,y1,x2,y2=wide[i]
    x3,y3,x4,y4=wide[i+1]
    if check_intersection(x1,y1,x2,y2,x3,y3,x4,y4):
        ans="NO"

if wide:
    for i in range(0,len(height)):
        x1,y1,x2,y2=height[i]
        x3,y3,x4,y4=wide[0]
        if check_intersection(x1,y1,x2,y2,x3,y3,x4,y4):
            ans="NO"
 
for i in range(len(height)):
    x1,y1,x2,y2=height[i]
    if X[0]:
        start=0
        end=len(X[0])-1
        while end-start>1:
            test=(end+start)//2
            if y1>=X[0][test][1]:
                start=test
            else:
                end=test
 
        if y1>=X[0][end][1]:
            index=end
        elif y1>=X[0][start][1]:
            index=start
        else:
            index=-1
        if index!=-1:
            x3,y3,x4,y4=X[0][index]
            if y4>=y1:
                ans="NO"
 
    if y2==0 and Y[0]:
        start=0
        end=len(Y[0])-1
        while end-start>1:
            test=(end+start)//2
            if x2>=Y[0][test][0]:
                start=test
            else:
                end=test
 
        if x2>=Y[0][end][0]:
            index=end
        elif x2>=Y[0][start][0]:
            index=start
        else:
            index=-1
        if index!=-1:
            x3,y3,x4,y4=Y[0][index]
            if x4>=x2:
                ans="NO"
 
    if y2==C and Y[C]:
        start=0
        end=len(Y[C])-1
        while end-start>1:
            test=(end+start)//2
            if x2>=Y[C][test][0]:
                start=test
            else:
                end=test
 
        if x2>=Y[C][end][0]:
            index=end
        elif x2>=Y[C][start][0]:
            index=start
        else:
            index=-1
        if index!=-1:
            x3,y3,x4,y4=Y[C][index]
            if x4>=x2:
                ans="NO"
 
    if x2==R and X[R]:
        start=0
        end=len(X[R])-1
        while end-start>1:
            test=(end+start)//2
            if y2>=X[R][test][1]:
                start=test
            else:
                end=test
 
        if y2>=X[R][end][1]:
            index=end
        elif y2>=X[R][start][1]:
            index=start
        else:
            index=-1
        if index!=-1:
            x3,y3,x4,y4=X[R][index]
            if y4>=y2:
                ans="NO"
 
 
for i in range(0,len(wide)):
    x1,y1,x2,y2=wide[i]
    if Y[0]:
        start=0
        end=len(Y[0])-1
        while end-start>1:
            test=(end+start)//2
            if x1>=Y[0][test][0]:
                start=test
            else:
                end=test
 
        if x1>=Y[0][end][0]:
            index=end
        elif x1>=Y[0][start][0]:
            index=start
        else:
            index=-1
        if index!=-1:
            x3,y3,x4,y4=Y[0][index]
            if x4>=x1:
                ans="NO"
 
    if y2==C and Y[C]:
        start=0
        end=len(Y[C])-1
        while end-start>1:
            test=(end+start)//2
            if x2>=Y[C][test][0]:
                start=test
            else:
                end=test
 
        if x2>=Y[C][end][0]:
            index=end
        elif x2>=Y[C][start][0]:
            index=start
        else:
            index=-1
        if index!=-1:
            x3,y3,x4,y4=Y[C][index]
            if x4>=x2:
                ans="NO"
 
    if x2==R and X[R]:
        start=0
        end=len(X[R])-1
        while end-start>1:
            test=(end+start)//2
            if y2>=X[R][test][1]:
                start=test
            else:
                end=test
 
        if y2>=X[R][end][1]:
            index=end
        elif y2>=X[R][start][1]:
            index=start
        else:
            index=-1
        if index!=-1:
            x3,y3,x4,y4=X[R][index]
            if y4>=y2:
                ans="NO"


print(ans)

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=[]
node=set([])
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])
        node.add((x1,y1))
        node.add((x2,y2))

n=len(line)
for i in range(0,n):
    x1,y1,x2,y2=line[i]
    if x2<x1:
        x1,x2=x2,x1
        y1,y2=y2,y1
    elif x2==x1:
        if y2<y1:
            y1,y2=y2,y1
    line[i]=[x1,y1,x2,y2]

line.sort()
height=[]
wide=[]
X={0:[],R:[]}
Y={0:[],C:[]}
for i in range(0,n):
    x1,y1,x2,y2=line[i]
    if x1==0:
        if x2==0:
            X[0].append(line[i])
        else:
            height.append(line[i])
    elif x1==R:
        X[R].append(line[i])
    else:
        if y1==0 and y2==0:
            Y[0].append(line[i])
        elif y1==C and y2==C:
            Y[C].append(line[i])
        else:
            wide.append(line[i])

height.sort()
wide.sort()
X[0].sort()
X[R].sort()
Y[0].sort()
Y[C].sort()
ans="YES"
for i in range(len(height)-1):
    x1,y1,x2,y2=height[i]
    x3,y3,x4,y4=height[i+1]
    if check_intersection(x1,y1,x2,y2,x3,y3,x4,y4):
        ans="NO"


for i in range(len(wide)-1):
    x1,y1,x2,y2=wide[i]
    x3,y3,x4,y4=wide[i+1]
    if check_intersection(x1,y1,x2,y2,x3,y3,x4,y4):
        ans="NO"



print(ans)