Line Segment Intersection

import math


class Point:
    def __init__(self, x, y):
        self.x = x
        self.y = y

    def __sub__(self, other):
        return Point(self.x - other.x, self.y - other.y)

    def __eq__(self, other):
        return self.x == other.x and self.y == other.y


class Line:
    def __init__(self, a, b):
        self.a = a
        self.b = b


def cross_product(p, q):
    #x1y2 − x2y1
    return p.x * q.y - p.y * q.x


def from_the_line(p, s):
    #(p−s1)×(p−s2)
    return cross_product(p - s.a, p - s.b)


def on_the_line(p, s):
    return (cross_product(p - s.a, p - s.b) == 0 and (min(s.a.y, s.b.y) < p.y < max(s.a.y, s.b.y)) and
            (min(s.a.x, s.b.x) < p.x < max(s.a.x, s.b.x)))


def same_line(p, q):
    return on_the_line(p.a, q) or on_the_line(p.b, q) or on_the_line(q.a, p) or on_the_line(q.b, p)


def end_intersection(p, q):
    return p.a == q.a or p.a == q.b or p.b == q.b or p.b == q.a


def middle_intersection(p, q):
    return ((from_the_line(p.a, q) > 0) != (from_the_line(p.b, q) > 0) and
            (from_the_line(q.a, p) > 0) != (from_the_line(q.b, p) > 0))


n = int(input())
for i in range(n):
    x11, y11, x12, y12, x21, y21, x22, y22 = map(int, input().split())
    p1 = Point(x11, y11)
    p2 = Point(x12, y12)
    p3 = Point(x21, y21)
    p4 = Point(x22, y22)
    l1 = Line(p1, p2)
    l2 = Line(p3, p4)
    if same_line(l1, l2) or end_intersection(l1, l2) or middle_intersection(l1, l2):
        print('YES')
    else:
        print('NO')

Test 1

Verdict: TIME LIMIT EXCEEDED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED

Test 4

Verdict: ACCEPTED

Test 5

Verdict: ACCEPTED

Test 6

Verdict: ACCEPTED