Line Segment Intersection

import sys
from typing import List
from cmath import phase
from collections import namedtuple

# Debug function
def debug(*args):
    print("DEBUG:", ", ".join(str(arg) for arg in args), file=sys.stderr)

# Define a point and segment using complex numbers
Point = complex
Segment = namedtuple("Segment", ["p", "q"])

def crossproduct(a: Point, b: Point) -> int:
    return (a.conjugate() * b).imag

def on_segment(r: Point, s: Segment) -> bool:
    return (min(s.p.real, s.q.real) <= r.real <= max(s.p.real, s.q.real) and
            min(s.p.imag, s.q.imag) <= r.imag <= max(s.p.imag, s.q.imag))

def orientation(r: Point, s: Segment) -> int:
    val = crossproduct(r - s.p, r - s.q)
    debug("val:", val)
    if val == 0:
        return 0  # Collinear
    return 1 if val > 0 else 2  # 1 for clockwise, 2 for counterclockwise

def do_intersect(s1: Segment, s2: Segment) -> bool:
    o1 = orientation(s2.p, s1)
    o2 = orientation(s2.q, s1)
    o3 = orientation(s1.p, s2)
    o4 = orientation(s1.q, s2)
    
    debug("o1, o2, o3, o4:", o1, o2, o3, o4)
    
    # General case
    if o1 != o2 and o3 != o4:
        return True

    # Special cases
    if o1 == 0 and on_segment(s2.p, s1): return True
    if o2 == 0 and on_segment(s2.q, s1): return True
    if o3 == 0 and on_segment(s1.p, s2): return True
    if o4 == 0 and on_segment(s1.q, s2): return True

    return False

# Main function to read input and process each test case
def main():
    t = int(input().strip())
    tests = []

    for _ in range(t):
        x1, y1, x2, y2, x3, y3, x4, y4 = map(int, input().strip().split())
        s1 = Segment(Point(x1, y1), Point(x2, y2))
        s2 = Segment(Point(x3, y3), Point(x4, y4))
        tests.append((s1, s2))

    for s1, s2 in tests:
        if do_intersect(s1, s2):
            print("YES")
        else:
            print("NO")

if __name__ == "__main__":
    main()

Test 1

Verdict: ACCEPTED

DEBUG: val:, 97.0
DEBUG: val:, 49.0
DEBUG: val:, -103.0
DEBUG: val:, -55.0
DEBUG: o1, o2, o3, o4:, 1, 1, 2, 2
DEBUG: val:, 14.0
DEBUG: val:, -5.0
DEBUG: val:, -28.0
DEBUG: val:, -9.0
DEBUG: o1, o2, o3, o4:, 1, 2, 2, 2
DEBUG: val:, 36.0
DEBUG: val:, 86.0
DEBUG: val:, 27.0
DEBUG: val:, -23.0
DEBUG: o1, o2, o3, o4:, 1, 1, 1, 2
DEBUG: val:, 36.0
DEBUG: val:, 21.0
DEBUG: val:, 6.0
DEBUG: val:, 21.0
DEBUG: o1, o2, o3, o4:, 1, 1, 1, 1
DEBUG: val:, -78.0
DEBUG: val:, -102.0
DEBUG: val:, -27.0
DEBUG: val:, -3.0
DEBUG: o1, o2, o3, o4:, 2, 2, 2, 2
DEBUG: val:, -264.0
DEBUG: val:, 72.0
DEBUG: val:, 24.0
DEBUG: val:, -312.0
DEBUG: o1, o2, o3, o4:, 2, 1, 1, 2
DEBUG: val:, 27.0
DEBUG: val:, 66.0
DEBUG: val:, 6.0
DEBUG: val:, -33.0
DEBUG: o1, o2, o3, o4:, 1, 1, 1, 2
DEBUG: val:, 122.0
DEBUG: val:, -18.0
DEBUG: val:, -8.0
DEBUG: val:, 132.0
DEBUG: o1, o2, o3, o4:, 1, 2, 2, 1
DEBUG: val:, 48.0
DEBUG: val:, -12.0
DEBUG: val:, 18.0
DEBUG: val:, 78.0
DEBUG: o1, o2, o3, o4:, 1, 2, 1, 1
DEBUG: val:, -165.0
D...

Test 2

Verdict: ACCEPTED

DEBUG: val:, 1306516.0
DEBUG: val:, 1203881.0
DEBUG: val:, -55841.0
DEBUG: val:, 46794.0
DEBUG: o1, o2, o3, o4:, 1, 1, 2, 1
DEBUG: val:, 269688.0
DEBUG: val:, -312368.0
DEBUG: val:, 798647.0
DEBUG: val:, 1380703.0
DEBUG: o1, o2, o3, o4:, 1, 2, 1, 1
DEBUG: val:, 33712.0
DEBUG: val:, -711921.0
DEBUG: val:, -612941.0
DEBUG: val:, 132692.0
DEBUG: o1, o2, o3, o4:, 1, 2, 2, 1
DEBUG: val:, -38853.0
DEBUG: val:, -99853.0
DEBUG: val:, -83767.0
DEBUG: val:, -22767.0
DEBUG: o1, o2, o3, o4:, 2, 2, 2, 2
DEBUG: val:, 976125.0
DEBUG: val:, -1214432.0
DEBUG: val:, -899321.0
DEBUG: val:, 1291236.0
DEBUG: o1, o2, o3, o4:, 1, 2, 2, 1
DEBUG: val:, -95617.0
DEBUG: val:, -474310.0
DEBUG: val:, -1516539.0
DEBUG: val:, -1137846.0
DEBUG: o1, o2, o3, o4:, 2, 2, 2, 2
DEBUG: val:, 253405.0
DEBUG: val:, -590940.0
DEBUG: val:, -753022.0
DEBUG: val:, 91323.0
DEBUG: o1, o2, o3, o4:, 1, 2, 2, 1
DEBUG: val:, -280848.0
DEBUG: val:, -34090.0
DEBUG: val:, 672519.0
DEBUG: val:, 425761.0
DEBUG: o1, o2, o3, o4:, 2, 2, 1, 1
D...

Test 3

Verdict: TIME LIMIT EXCEEDED

Test 4

Verdict: TIME LIMIT EXCEEDED

Test 5

Verdict: ACCEPTED

DEBUG: val:, -10.0
DEBUG: val:, 5000000000.0
DEBUG: val:, 4999999980.0
DEBUG: val:, 0.0
DEBUG: o1, o2, o3, o4:, 2, 1, 1, 0

Test 6

Verdict: ACCEPTED

DEBUG: val:, 1.0
DEBUG: val:, 1000000000.0
DEBUG: val:, 0.0
DEBUG: val:, -1000000000.0
DEBUG: o1, o2, o3, o4:, 1, 1, 0, 2