Line Segment Intersection

def on_segment(x1, y1, x2, y2, x3, y3):
    return min(x1, x2) <= x3 <= max(x1, x2) and min(y1, y2) <= y3 <= max(y1, y2)

def orientation(x1, y1, x2, y2, x3, y3):
    val = (y2 - y1) * (x3 - x2) - (x2 - x1) * (y3 - y2)
    if val == 0:
        return 0
    return 1 if val > 0 else 2

def intersect(x1, y1, x2, y2, x3, y3, x4, y4):
    o1 = orientation(x1, y1, x2, y2, x3, y3)
    o2 = orientation(x1, y1, x2, y2, x4, y4)
    o3 = orientation(x3, y3, x4, y4, x1, y1)
    o4 = orientation(x3, y3, x4, y4, x2, y2)

    if o1 != o2 and o3 != o4:
        return True

    if o1 == 0 and on_segment(x1, y1, x2, y2, x3, y3): return True
    if o2 == 0 and on_segment(x1, y1, x2, y2, x4, y4): return True
    if o3 == 0 and on_segment(x3, y3, x4, y4, x1, y1): return True
    if o4 == 0 and on_segment(x3, y3, x4, y4, x2, y2): return True

    return False

def solve(test_cases):
    results = []
    for x1, y1, x2, y2, x3, y3, x4, y4 in test_cases:
        results.append("YES" if intersect(x1, y1, x2, y2, x3, y3, x4, y4) else "NO")
    return results

# Example usage
test_cases = [
    (1, 1, 5, 3, 1, 2, 4, 3),
    (1, 1, 5, 3, 1, 1, 4, 3),
    (1, 1, 5, 3, 2, 3, 4, 1),
    (1, 1, 5, 3, 2, 4, 4, 1),
    (1, 1, 5, 3, 3, 2, 7, 4)
]
print(solve(test_cases))

Test 1

Verdict: WRONG ANSWER

Test 2

Verdict: WRONG ANSWER

Test 3

Verdict: WRONG ANSWER

Test 4

Verdict: WRONG ANSWER

Test 5

Verdict: WRONG ANSWER

Test 6

Verdict: WRONG ANSWER