Submission #5545094

---

Source Code Expand

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

Submission Info

Judge Result