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))

if len(node)!=len(line)*2:
    print("NO")
    exit()

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")

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))

if len(node)!=len(line)*2:
    print("NO")
    exit()

def condition():
    global 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)) and not (x1==x2==0 or x1==x2==R):
            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)) and not (y1==y2==0 or y1==y2==C):
            yaxis=False
            break

    if xaxis:
        X={0:[],C:[]}
        last={0:[], R:[]}
        irr=set([])
        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:
                        X[0].append(line[i])
            elif y1==C:
                if y2!=C:
                    X[C].append(line[i])
                else:
                    if x1>x2:
                        X[C].append([x2,y2,x1,y1])
                    else:
                        X[C].append(line[i])
            elif y2==0:
                X[0].append([x2,y2,x1,y1])
            elif y2==C:
                X[C].append([x2,y2,x1,y1])
            else:
                if y1<y2:
                    last[x1].append([x1,y1,"R"])
                    last[x2].append([x2,y2,"L"])
                else:
                    line[i]=[x2,y2,x1,y1]
                    last[x1].append([x1,y1,"L"])
                    last[x2].append([x2,y2,"R"])
                irr.add((line[i][0],line[i][1],line[i][2],line[i][3]))

        m=len(X[0])
        k=len(X[C])
        l=len(last[0])
        p=len(last[R])
        X[0].sort()
        X[C].sort()
        last[0].sort()
        last[R].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()

        for i in range(0,l-1):
            if last[0][i][2]=="R" and last[0][i+1][2]=="L":
                check=(last[0][i][0],last[0][i][1],last[0][i+1][0],last[0][i+1][1])
                if check not in irr:
                    print("NO")
                    exit()
            else:
                print("NO")
                exit()

        for i in range(0,p-1):
            if last[R][i][2]=="R" and last[R][i+1][2]=="L":
                check=(last[R][i][0],last[R][i][1],last[R][i+1][0],last[R][i+1][1])
                if check not in irr:
                    print("NO")
                    exit()
            else:
                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>=x2>=x3:
                                    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>=x2>=x3:
                                    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 y3==y4:
                            if x4>=x2>=x3:
                                print("NO")
                                exit()

                    if index!=m:
                        x3,y3,x4,y4=X[0][index]
                        if y3==y4:
                            if x4>=x2>=x3:
                                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()
    else:
        print("NO")
        exit()

condition()

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))

if len(node)!=len(line)*2:
    print("NO")
    exit()

def condition():
    global 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)) and not (x1==x2==0 or x1==x2==R):
            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)) and not (y1==y2==0 or y1==y2==C):
            yaxis=False
            break

    if xaxis:
        X={0:[],C:[]}
        last={0:[], R:[]}
        irr=set([])
        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:
                        X[0].append(line[i])
            elif y1==C:
                if y2!=C:
                    X[C].append(line[i])
                else:
                    if x1>x2:
                        X[C].append([x2,y2,x1,y1])
                    else:
                        X[C].append(line[i])
            elif y2==0:
                X[0].append([x2,y2,x1,y1])
            elif y2==C:
                X[C].append([x2,y2,x1,y1])
            else:
                if y1<y2:
                    last[x1].append([x1,y1,"R"])
                    last[x2].append([x2,y2,"L"])
                else:
                    line[i]=[x2,y2,x1,y1]
                    last[x1].append([x1,y1,"L"])
                    last[x2].append([x2,y2,"R"])
                irr.add((line[i][0],line[i][1],line[i][2],line[i][3]))

        m=len(X[0])
        k=len(X[C])
        l=len(last[0])
        p=len(last[R])
        X[0].sort()
        X[C].sort()
        last[0].sort()
        last[R].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()

        for i in range(0,l-1):
            if last[0][i][2]=="R" and last[0][i+1][2]=="L":
                check=(last[0][i][0],last[0][i][1],last[0][i+1][0],last[0][i+1][1])
                if check not in irr:
                    print("NO")
                    exit()
            else:
                print("NO")
                exit()

        for i in range(0,p-1):
            if last[R][i][2]=="R" and last[R][i+1][2]=="L":
                check=(last[R][i][0],last[R][i][1],last[R][i+1][0],last[R][i+1][1])
                if check not in irr:
                    print("NO")
                    exit()
            else:
                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>=x2>=x3:
                                    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>=x2>=x3:
                                    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 y3==y4:
                            if x4>=x2>=x3:
                                print("NO")
                                exit()

                    if index!=m:
                        x3,y3,x4,y4=X[0][index]
                        if y3==y4:
                            if x4>=x2>=x3:
                                print("NO")
                                exit()

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

                    if last[0][start][1]>=y2:
                        index=start
                    elif last[0][end][1]>=y2:
                        index=end
                    else:
                        index=l

                    if l>index>0:
                        if (last[0][index-1][2],last[0][index][2])!=("R","L"):
                            print("NO")
                            exit()

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

                    if last[0][start][1]>=y2:
                        index=start
                    elif last[0][end][1]>=y2:
                        index=end
                    else:
                        index=l

                    if l>index>0:
                        if (last[0][index-1][2],last[0][index][2])!=("R","L"):
                            print("NO")
                            exit()

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

                    if last[R][start][1]>=y2:
                        index=start
                    elif last[R][end][1]>=y2:
                        index=end
                    else:
                        index=l

                    if l>index>0:
                        if (last[R][index-1][2],last[R][index][2])!=("R","L"):
                            print("NO")
                            exit()

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

                    if last[R][start][1]>=y2:
                        index=start
                    elif last[R][end][1]>=y2:
                        index=end
                    else:
                        index=l

                    if l>index>0:
                        if (last[R][index-1][2],last[R][index][2])!=("R","L"):
                            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()
    else:
        print("NO")
        exit()

condition()