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

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED

Test 4

Verdict: ACCEPTED

Test 5

Verdict: ACCEPTED

Test 6

Verdict: ACCEPTED