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=[]
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"



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

for i in range(len(Y[C])-1):
    x1,y1,x2,y2=Y[C][i]
    x3,y3,x4,y4=Y[C][i+1]
    if y1!=C or y2!=C or y3!=C or y4!=C:
        print("YES")
        exit()
    if max(x2,x1)>=x3>=min(x1,x2) or max(x2,x1)>=x4>=min(x1,x2):
        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"



for i in range(len(Y[0])-1):
    x1,y1,x2,y2=Y[0][i]
    x3,y3,x4,y4=Y[0][i+1]
    if y1!=0 or y2!=0 or y3!=0 or y4!=0:
        print("YES")
        exit()
    a=max(x1,x2)
    b=min(x3,x4)
    if a>=b:
        ans="NO"


for i in range(len(Y[C])-1):
    x1,y1,x2,y2=Y[C][i]
    x3,y3,x4,y4=Y[C][i+1]
    if y1!=C or y2!=C or y3!=C or y4!=C:
        print("YES")
        exit()
    a=max(x1,x2)
    b=min(x3,x4)
    if a>=b:
        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"



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


for i in range(len(Y[C])-1):
    x1,y1,x2,y2=Y[C][i]
    x3,y3,x4,y4=Y[C][i+1]
    a=max(x1,x2)
    b=min(x3,x4)
    if a>=b:
        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"



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


for i in range(len(Y[C])-1):
    x1,y1,x2,y2=Y[C][i]
    x3,y3,x4,y4=Y[C][i+1]
    if x2>=x3>=x1:
        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==y2==0:
            Y[0].append(line[i])
        elif y1==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(Y[0])-1):
    x1,y1,x2,y2=Y[0][i]
    x3,y3,x4,y4=Y[0][i+1]
    if x2>=x3>=x1:
        ans="NO"


for i in range(len(Y[C])-1):
    x1,y1,x2,y2=Y[C][i]
    x3,y3,x4,y4=Y[C][i+1]
    if x2>=x3>=x1:
        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==y2==0:
            Y[0].append(line[i])
        elif y1==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()

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):
        print("NO")
        exit()

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):
        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 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 x2>=x3>=x1:
        print("NO")
        exit()

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=[]
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==y2==0:
            Y[0].append(line[i])
        elif y1==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()

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):
        print("NO")
        exit()

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):
        print("NO")
        exit()

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

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:
                print("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:
                print("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:
                print("NO")
                exit()

    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:
                print("NO")
                exit()


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:
                print("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:
                print("NO")
                exit()

    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:
                print("NO")
                exit()


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=[]
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==y2==0:
            Y[0].append(line[i])
        elif y1==y2==C:
            Y[C].append(line[i])
        else:
            wide.append(line[i])


for i in range(0,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):
        print("NO")
        exit()

for i in range(0,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):
        print("NO")
        exit()


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=[]
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==y2==0:
            Y[0].append(line[i])
        elif y1==y2==C:
            Y[C].append(line[i])
        else:
            wide.append(line[i])


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):
        print("NO")
        exit()

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):
        print("NO")
        exit()

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

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=[]
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==y2==0:
            Y[0].append(line[i])
        elif y1==y2==C:
            Y[C].append(line[i])
        else:
            wide.append(line[i])


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):
        print("NO")
        exit()

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):
        print("NO")
        exit()

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

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:
                print("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:
                print("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:
                print("NO")
                exit()

    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:
                print("NO")
                exit()


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:
                print("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:
                print("NO")
                exit()

    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:
                print("NO")
                exit()


print("YES")