Problem:


Intersection

For given two segments s1 and s2, print "1" if they are intersect, "0" otherwise.

s1 is formed by end points p0 and p1, and
s2 is formed by end points p2 and p3.

Input

The entire input looks like:

q (the number of queries)
1st query
2nd query
...
qth query

Each query consists of integer coordinates of end points of s1 and s2 in the following format:

xp0 yp0 xp1 yp1 xp2 yp2 xp3 yp3

Output

For each query, print "1" or "0".

Constraints

1 ≤ q ≤ 1000

-10000 ≤ xpi, ypi ≤ 10000

p0 &ne; p1 and
p2 &ne; p3.

Sample Input 1

3
0 0 3 0 1 1 2 -1
0 0 3 0 3 1 3 -1
0 0 3 0 3 -2 5 0

Sample Output 1

1
1
0



Sample input:
3
0 0 3 0 1 1 2 -1
0 0 3 0 3 1 3 -1
0 0 3 0 3 -2 5 0


Sample output:
1
1
0

Submission status: Accepted

Solution code:
from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp(): return int(input())
def inpl(): return list(map(int, input().split()))
def inpl_str(): return list(input().split())

###########################
#          幾何
###########################
def sgn(a):
    if a < -eps: return -1
    if a >  eps: return  1
    return 0

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

    def tolist(self):
        return [self.x,self.y]

    def __add__(self,p):
        return Point(self.x+p.x, self.y+p.y)
    def __iadd__(self,p):
        return self + p

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

    def __truediv__(self,n):
        return Point(self.x/n, self.y/n)
    def __itruediv__(self,n):
        return self / n

    def __mul__(self,n):
        return Point(self.x*n, self.y*n)
    def __imul__(self,n):
        return self * n

    def __lt__(self,other):
        tmp = sgn(self.x - other.x)
        if tmp != 0:
            return tmp < 0
        else:
            return sgn(self.y - other.y) < 0

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

    def abs(self):
        return math.sqrt(self.x**2+self.y**2)

    def dot(self,p):
        return self.x * p.x + self.y*p.y

    def det(self,p):
        return self.x * p.y - self.y*p.x

    def arg(self,p):
        return math.atan2(y,x)

# 点の進行方向 a -> b -> c
def iSP(a,b,c):
    tmp = sgn((b-a).det(c-a))
    if tmp > 0:   return 1   # 左に曲がる場合
    elif tmp < 0: return -1  # 右に曲がる場合
    else: # まっすぐ
        if sgn((b-a).dot(c-a)) < 0: return -2 # c-a-b の順
        if sgn((a-b).dot(c-b)) < 0: return  2 # a-b-c の順
        return 0 # a-c-bの順

# ab,cd の直線交差
def isToleranceLine(a,b,c,d):
    if sgn((b-a).det(c-d)) != 0: return 1 # 交差する
    else:
        if sgn((b-a).det(c-a)) != 0: return 0 # 平行
        else: return -1 # 同一直線

# ab,cd の線分交差 重複，端点での交差もTrue
def isToleranceSegline(a,b,c,d):
    return sgn(iSP(a,b,c)*iSP(a,b,d))<=0 and sgn(iSP(c,d,a)*iSP(c,d,b)) <= 0

# 直線ab と 直線cd の交点 (存在する前提)
def Intersection(a,b,c,d):
    tmp1 = (b-a)*((c-a).det(d-c))
    tmp2 = (b-a).det(d-c)
    return a+(tmp1/tmp2)

# 直線ab と 点c の距離
def DistanceLineToPoint(a,b,c):
    return abs(((c-a).det(b-a))/((b-a).abs()))

# 線分ab と 点c の距離
def DistanceSeglineToPoint(a,b,c):
    if sgn((b-a).dot(c-a)) < 0: # <cab が鈍角
        return (c-a).abs()
    if sgn((a-b).dot(c-b)) < 0: # <cba が鈍角
        return (c-b).abs()
    return DistanceLineToPoint(a,b,c)

# 直線ab への 点c からの垂線の足
def Vfoot(a,b,c):
    d = c + Point((b-a).y,-(b-a).x)
    return Intersection(a,b,c,d)

# 多角形の面積
def PolygonArea(Plist):
    Plist = ConvexHull(Plist)
    L = len(Plist)
    S = 0
    for i in range(L):
        tmpS = (Plist[i-1].det(Plist[i]))/2
        S += tmpS
    return S

# 多角形の重心
def PolygonG(Plist):
    Plist = ConvexHull(Plist)
    L = len(Plist)
    S = 0
    G = Point(0,0)
    for i in range(L):
        tmpS = (Plist[i-1].det(Plist[i]))/2
        S += tmpS
        G += (Plist[i-1]+Plist[i])/3*tmpS
    return G/S

# 凸法
def ConvexHull(Plist):
    Plist.sort()
    L = len(Plist)
    qu = deque([])
    quL = 0
    for p in Plist:
        while quL >= 2 and iSP(qu[quL-2],qu[quL-1],p) == 1:
            qu.pop()
            quL -= 1
        qu.append(p)
        quL += 1

    qd = deque([])
    qdL = 0
    for p in Plist:
        while qdL >= 2 and iSP(qd[qdL-2],qd[qdL-1],p) == -1:
            qd.pop()
            qdL -= 1
        qd.append(p)
        qdL += 1

    qd.pop()
    qu.popleft()
    hidari = list(qd) + list(reversed(qu)) # 左端開始，左回りPlist
    return hidari

N = int(input())
for _ in range(N):
    x0,y0,x1,y1,x2,y2,x3,y3 = inpl()
    p0 = Point(x0,y0)
    p1 = Point(x1,y1)
    p2 = Point(x2,y2)
    p3 = Point(x3,y3)
    if isToleranceSegline(p0,p1,p2,p3):
        print(1)
    else:
        print(0)

Submission status: Accepted

Solution code:
n = int(input())

def z(x,  y,  x1,  y1,  x2,  y2):
    if (x1 > x2):x1,x2=x2,x1;y1,y2=y2,y1
    return x1 <= x and x <= x2 and ((y1 <= y2 and y1 <= y and y <= y2) | (y1 > y2 and y2 <= y and y <= y1)) and (y-y1)*(x2-x1) == (y2-y1)*(x-x1);

for i in range(n):
    a,b,c,d,e,f,g,h = map(int, input().split())
    
    p = d-b
    q = c-a
    r = h-f
    s = g-e
    
    t = (f-b)*q - (e-a)*p
    u = (h-b)*q - (g-a)*p
    
    v = (b-f)*s - (a-e)*r
    w = (d-f)*s - (c-e)*r

    if (t*u<0 and v*w<0) | z(a,b,e,f,g,h) | z(c,d,e,f,g,h) | z(e,f,a,b,c,d) | z(g,h,a,b,c,d):
        print(1)
    else:
        print(0)

Submission status: Accepted

Solution code:
import math


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

    def __add__(self, v):
        return Vector2(self.x+v.x, self.y+v.y)

    def __sub__(self, v):
        return Vector2(self.x-v.x, self.y-v.y)

    def __mul__(self, v):
        return Vector2(self.x*v, self.y*v)

    def __truediv__(self, v):
        return Vector2(self.x/v, self.y/v)

    def __abs__(self):
        return math.sqrt(float(self.x*self.x+self.y*self.y))

    def dot(self, v):
        return self.x*v.x+self.y*v.y

    def cross(self, v):
        return self.x*v.y-self.y*v.x

    def norm(self):
        d = abs(self)
        return Vector2(self.x/d, self.y/d)


def distanceLP(v1, v2, p):
    '''
    v1 -> v2の直線とpとの距離
    '''
    return abs((v2-v1).cross(p-v1))/abs(v2-v1)


def distanceSP(v1, v2, p):
    '''
    v1 -> v2の線分とpとの距離
    '''
    if (v2-v1).dot(p-v1) < 0.0:
        return abs(p-v1)
    if (v1-v2).dot(p-v2) < 0.0:
        return abs(p-v2)
    return distanceLP(v1, v2, p)


def intersect(p1, p2, p3, p4):
    '''
    p1p2とp3p4の交差判定
    '''
    #t1 = (p1.x-p2.x)*(p3.y-p1.y)+(p1.y-p2.y)*(p1.x-p3.x)
    #t2 = (p1.x-p2.x)*(p4.y-p1.y)+(p1.y-p2.y)*(p1.x-p4.x)
    #t3 = (p3.x-p4.x)*(p1.y-p3.y)+(p3.y-p4.y)*(p3.x-p1.x)
    #t4 = (p3.x-p4.x)*(p2.y-p3.y)+(p3.y-p4.y)*(p3.x-p2.x)
    # return (t1*t2) <= 0.0 and (t3*t4) <= 0.0
    c1 = ccw(p1, p2, p3)*ccw(p1, p2, p4)
    c2 = ccw(p3, p4, p1)*ccw(p3, p4, p2)
    return c1 <= 0.0 and c2 <= 0.0


def distance(a1, a2, b1, b2):
    '''
    線分a1a2とb1b2の距離
    '''
    if intersect(a1, a2, b1, b2):
        return 0.0
    return min([
        min([distanceSP(a1, a2, b1), distanceSP(a1, a2, b2)]),
        min([distanceSP(b1, b2, a1), distanceSP(b1, b2, a2)])
    ])


def ccw(p0, p1, p2):
    c = (p1-p0).cross(p2-p0)
    if math.isclose(c, 0.0, abs_tol=1e-10):
        d = (p1-p0).dot(p2-p0)
        if d < 0.0:
            return 1
        else:
            d1 = abs(p1-p0)
            d2 = abs(p2-p0)
            if d1 < d2:
                return -1
            else:
                return 0
    elif c < 0.0:
        return -1
    else:
        return 1


q = int(input())
for i in range(q):
    x0, y0, x1, y1, x2, y2, x3, y3 = map(int, input().split())
    p0 = Vector2(x0, y0)
    p1 = Vector2(x1, y1)
    p2 = Vector2(x2, y2)
    p3 = Vector2(x3, y3)
    print("1" if intersect(p0, p1, p2, p3) else "0")

Submission status: Accepted

Solution code:
#! /usr/bin/env python3

from typing import List, Tuple
from math import sqrt
from enum import IntEnum

EPS = 1e-10


def float_equal(x: float, y: float) -> bool:
    return abs(x - y) < EPS


class PointLocation(IntEnum):
    COUNTER_CLOCKWISE = 1
    CCW = 1
    CLOCKWISE = -1
    CW = -1
    ONLINE_BACK = 2
    O_B = 2
    ONLINE_FRONT = -2
    O_F = -2
    ON_SEGMENT = 0
    O_S = 0


PL = PointLocation


class Point:

    def __init__(self, x: float=0.0, y: float=0.0) -> None:
        self.x = x
        self.y = y

    def __repr__(self) -> str:
        return "Point({}, {})".format(self.x, self.y)

    def __eq__(self, other: object) -> bool:
        if not isinstance(other, Point):
            # print("NotImplemented in Point")
            return NotImplemented
        return float_equal(self.x, other.x) and \
            float_equal(self.y, other.y)

    def __add__(self, other: 'Point') -> 'Point':
        return Point(self.x + other.x, self.y + other.y)

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

    def __mul__(self, k: float) -> 'Point':
        return Point(self.x * k, self.y * k)

    def __rmul__(self, k: float) -> 'Point':
        return self * k

    def __truediv__(self, k: float) -> 'Point':
        return Point(self.x / k, self.y / k)

    def __lt__(self, other: 'Point') -> bool:
        return self.y < other.y \
            if abs(self.x - other.x) < EPS \
            else self.x < other.x

    def norm(self):
        return self.x * self.x + self.y * self.y

    def abs(self):
        return sqrt(self.norm())

    def dot(self, other: 'Point') -> float:
        return self.x * other.x + self.y * other.y

    def cross(self, other: 'Point') -> float:
        return self.x * other.y - self.y * other.x

    def is_orthogonal(self, other: 'Point') -> bool:
        return float_equal(self.dot(other), 0.0)

    def is_parallel(self, other: 'Point') -> bool:
        return float_equal(self.cross(other), 0.0)

    def distance(self, other: 'Point') -> float:
        return (self - other).abs()

    def in_side_of(self, seg: 'Segment') -> bool:
        return seg.vector().dot(
            Segment(seg.p1, self).vector()) >= 0

    def in_width_of(self, seg: 'Segment') -> bool:
        return \
            self.in_side_of(seg) and \
            self.in_side_of(seg.reverse())

    def distance_to_line(self, seg: 'Segment') -> float:
        return \
            abs((self - seg.p1).cross(seg.vector())) / \
            seg.length()

    def distance_to_segment(self, seg: 'Segment') -> float:
        if not self.in_side_of(seg):
            return self.distance(seg.p1)
        if not self.in_side_of(seg.reverse()):
            return self.distance(seg.p2)
        else:
            return self.distance_to_line(seg)

    def location(self, seg: 'Segment') -> PointLocation:
        p = self - seg.p1
        d = seg.vector().cross(p)
        if d > EPS:
            return PointLocation.COUNTER_CLOCKWISE
        if d < -EPS:
            return PointLocation.CLOCKWISE
        if seg.vector().dot(p) < 0.0:
            return PointLocation.ONLINE_BACK
        if seg.vector().norm() < p.norm():
            return PointLocation.ONLINE_FRONT
        return PointLocation.ON_SEGMENT


Vector = Point


class Segment:

    def __init__(self, p1: Point = None, p2: Point = None) -> None:
        self.p1: Point = Point() if p1 is None else p1
        self.p2: Point = Point() if p2 is None else p2

    def __repr__(self) -> str:
        return "Segment({}, {})".format(self.p1, self.p2)

    def __eq__(self, other: object) -> bool:
        if not isinstance(other, Segment):
            # print("NotImplemented in Segment")
            return NotImplemented
        return self.p1 == other.p1 and self.p2 == other.p2

    def vector(self) -> Vector:
        return self.p2 - self.p1

    def reverse(self) -> 'Segment':
        return Segment(self.p2, self.p1)

    def length(self) -> float:
        return self.p1.distance(self.p2)

    def is_orthogonal(self, other: 'Segment') -> bool:
        return self.vector().is_orthogonal(other.vector())

    def is_parallel(self, other: 'Segment') -> bool:
        return self.vector().is_parallel(other.vector())

    def projection(self, p: Point) -> Point:
        v = self.vector()
        vp = p - self.p1
        return v.dot(vp) / v.norm() * v + self.p1

    def reflection(self, p: Point) -> Point:
        x = self.projection(p)
        return p + 2 * (x - p)

    def intersect_ratio(self, other: 'Segment') -> Tuple[float, float]:
        a = self.vector()
        b = other.vector()
        c = self.p1 - other.p1
        s = b.cross(c) / a.cross(b)
        t = a.cross(c) / a.cross(b)
        return s, t

    def intersects(self, other: 'Segment') -> bool:
        d0 = self.p1.location(other)
        d1 = self.p2.location(other)
        d2 = other.p1.location(self)
        d3 = other.p2.location(self)
        return d0 * d1 * d2 * d3 == 0 or \
            (d0 * d1 == -1 and d2 * d3 == -1)

    def intersection(self, other: 'Segment') -> Point:
        s, _ = self.intersect_ratio(other)
        return self.p1 + s * self.vector()

    def distance_with_segment(self, other: 'Segment') -> float:
        if not self.is_parallel(other) and \
                self.intersects(other):
            return 0
        else:
            return min(
                self.p1.distance_to_segment(other),
                self.p2.distance_to_segment(other),
                other.p1.distance_to_segment(self),
                other.p2.distance_to_segment(self))


Line = Segment


class Circle:

    def __init__(self, c: Point=None, r: float=0.0) -> None:
        self.c: Point = Point() if c is None else c
        self.r: float = r

    def __eq__(self, other: object) -> bool:
        if not isinstance(other, Circle):
            return NotImplemented
        return self.c == other.c and self.r == other.r

    def __repr__(self) -> str:
        return "Circle({}, {})".format(self.c, self.r)

def main() -> None:
    q = int(input())

    for _ in range(q):
        x0, y0, x1, y1, x2, y2, x3, y3 = \
            [int(x) for x in input().split()]
        s1 = Segment(Point(x0, y0), Point(x1, y1))
        s2 = Segment(Point(x2, y2), Point(x3, y3))
        print(1 if s1.intersects(s2) else 0)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def dot(vx1, vy1, vx2, vy2):
    return vx1*vx2 + vy1*vy2


def cross(vx1, vy1, vx2, vy2):
    return vx1*vy2 - vy1*vx2


q = int(input())

for _ in range(q):
    x0, y0, x1, y1, x2, y2, x3, y3 = map(int, input().split())

    c1 = cross(x1 - x0, y1 - y0, x2 - x0, y2 - y0)
    c2 = cross(x1 - x0, y1 - y0, x3 - x0, y3 - y0)
    c3 = cross(x3 - x2, y3 - y2, x0 - x2, y0 - y2)
    c4 = cross(x3 - x2, y3 - y2, x1 - x2, y1 - y2)
    d1 = dot(x1 - x0, y1 - y0, x2 - x0, y2 - y0)
    d2 = dot(x1 - x0, y1 - y0, x3 - x0, y3 - y0)
    d3 = dot(x0 - x1, y0 - y1, x2 - x1, y2 - y1)
    d4 = dot(x0 - x1, y0 - y1, x3 - x1, y3 - y1)

    if c1*c2 <= 0 and c3*c4 <= 0:
        if (d1 < 0 and d2 < 0) or (d3 < 0 and d4 < 0):
            print(0)
        else:
            print(1)
    else:
        print(0)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
# CGL_2_B: Segments/Lines - Intersection

from math import sqrt


class Segment:
    def __init__(self, p0, p1):
        self.end_points = (p0, p1)

    def intersect(self, other):
        p0, p1 = self.end_points
        p2, p3 = other.end_points

        if convex(p0, p2, p1, p3):
            return True
        else:
            if (p0 in other or p1 in other
                    or p2 in self or p3 in self):
                return True

        return False

    def __contains__(self, p):
        p0, p1 = self.end_points
        x0, y0 = p0
        x1, y1 = p1
        x, y = p
        v = (x1-x0, y1-y0)
        v0 = (x-x0, y-y0)
        v1 = (x-x1, y-y1)
        if dot(orthogonal(v0), v1) == 0:
            if abs(length(v0) + length(v1) - length(v)) < 1e-10:
                return True
        return False


def dot(v1, v2):
    x1, y1 = v1
    x2, y2 = v2
    return x1 * x2 + y1 * y2


def orthogonal(v):
    x, y = v
    return -y, x


def length(v):
    x, y = v
    return sqrt(x**2 + y**2)


def convex(p0, p1, p2, p3):
    ret = []
    for pa, pb, pc in zip([p0, p1, p2, p3],
                          [p1, p2, p3, p0],
                          [p2, p3, p0, p1]):
        xa, ya = pa
        xb, yb = pb
        xc, yc = pc
        v1 = (xb - xa, yb - ya)
        v2 = (xc - xb, yc - yb)
        ret.append(dot(orthogonal(v1), v2))

    return all([d > 0 for d in ret]) or all([d < 0 for d in ret])


def run():
    q = int(input())

    for _ in range(q):
        x0, y0, x1, y1, x2, y2, x3, y3 = [int(i) for i in input().split()]
        s1 = Segment((x0, y0), (x1, y1))
        s2 = Segment((x2, y2), (x3, y3))
        if s1.intersect(s2):
            print(1)
        else:
            print(0)


if __name__ == '__main__':
    run()

Submission status: Accepted

Solution code:
import math
from typing import Union


class Point(object):
    __slots__ = ['x', 'y']

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

    def __add__(self, other):
        return Point(self.x + other.x, self.y + other.y)

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

    def __mul__(self, other: Union[int, float]):
        return Point(self.x * other, self.y * other)

    def __repr__(self):
        return f"({self.x},{self.y})"


class Vector(Point):
    __slots__ = ['x', 'y', 'pt1', 'pt2']

    def __init__(self, pt1: Point, pt2: Point):
        from_pt1_to_pt2 = pt2 - pt1
        super().__init__(from_pt1_to_pt2.x, from_pt1_to_pt2.y)
        self.pt1 = pt1
        self.pt2 = pt2

    def dot(self, other):
        return self.x * other.x + self.y * other.y

    def cross(self, other):
        return self.x * other.y - self.y * other.x

    def norm(self):
        return pow(self.x, 2) + pow(self.y, 2)

    def abs(self):
        return math.sqrt(self.norm())

    def __repr__(self):
        return f"{self.pt1},{self.pt2}"


class Segment(Vector):
    __slots__ = ['x', 'y', 'pt1', 'pt2']

    def __init__(self, pt1: Point, pt2: Point):
        super().__init__(pt1, pt2)

    def projection(self, pt: Point)-> Point:
        t = self.dot(Vector(self.pt1, pt)) / pow(self.abs(), 2)
        return Point(self.pt1.x + t * self.x, self.pt1.y + t * self.y)

    def reflection(self, pt: Point) -> Point:
        return self.projection(pt) * 2 - pt

    def is_intersected_with(self, other) -> bool:
        if (self.point_geometry(other.pt1) * self.point_geometry(other.pt2)) <= 0\
                and other.point_geometry(self.pt1) * other.point_geometry(self.pt2) <= 0:
            return True
        else:
            return False

    def point_geometry(self, pt: Point) -> int:
        """
        [-2:"Online Back", -1:"Counter Clockwise", 0:"On Segment", 1:"Clockwise",  2:"Online Front"]
        """
        vec_pt1_to_pt = Vector(self.pt1, pt)
        cross = self.cross(vec_pt1_to_pt)
        if cross > 0:
            return -1   # counter clockwise
        elif cross < 0:
            return 1    # clockwise
        else:           # cross == 0
            dot = self.dot(vec_pt1_to_pt)
            if dot < 0:
                return -2    # online back
            else:       # dot > 0
                if self.abs() < vec_pt1_to_pt.abs():
                    return 2    # online front
                else:
                    return 0    # on segment

    def __repr__(self):
        return f"{self.pt1},{self.pt2}"


def main():
    num_query = int(input())
    for i in range(num_query):
        p0_x, p0_y, p1_x, p1_y, p2_x, p2_y, p3_x, p3_y = map(int, input().split())
        seg_1 = Segment(Point(p0_x, p0_y), Point(p1_x, p1_y))
        seg_2 = Segment(Point(p2_x, p2_y), Point(p3_x, p3_y))

        print(int(seg_1.is_intersected_with(seg_2)))
    return


main()

Submission status: Accepted

Solution code:
def dot3(O, A, B):
  ox, oy = O
  ax, ay = A
  bx, by = B
  return (ax - ox) * (bx - ox) + (ay - oy) * (by - oy)

def cross3(O, A, B):
  ox, oy = O
  ax, ay = A
  bx, by = B
  return (ax - ox) * (by- oy) - (bx - ox) * (ay - oy)

def dist2(A, B):
  ax, ay = A
  bx, by = B
  return (ax - bx)**2 + (ay - by)**2

def is_intersection(p0, p1, q0, q1):
  c0 = cross3(p0, p1, q0)
  c1 = cross3(p0, p1, q1)
  d0 = cross3(q0, q1, p0)
  d1 = cross3(q0, q1, p1)
  if c0 == c1 == 0:
    e0 = dot3(p0, p1, q0)
    e1 = dot3(p0, p1, q1)
    if not e0 < e1:
      e0, e1 = e1, e0
    return e0 <= dist2(p0, p1) and 0 <= e1
  return c0 * c1 <= 0 and d0 * d1 <= 0

for q in range(int(input())):
  x0, y0, x1, y1, x2, y2, x3, y3 = map(int, input().split())
  print(+is_intersection((x0, y0), (x1, y1), (x2, y2), (x3, y3)))

Submission status: Accepted

Solution code:
import math

EPS = 1e-10

def equals(a, b):
    return abs(a - b) < EPS


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

    def __add__(self, p):
        return Point(self.x + p.x, self.y + p.y)

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

    def __mul__(self, a):
        return Point(self.x * a, self.y * a)

    def __rmul__(self, a):
        return self * a

    def __truediv__(self, a):
        return Point(self.x / a, self.y / a)

    def norm(self):
        return self.x * self.x + self.y * self.y

    def abs(self):
        return math.sqrt(self.norm())

    def __lt__(self, p):
        if self.x != p.x:
            return self. x < p.x
        else:
            return self.y < p.y

    def __eq__(self, p):
        return equals(self.x, p.x) and equals(self.y, p.y)


class Segment:
    def __init__(self, p1, p2):
        self.p1 = p1
        self.p2 = p2


def dot(a, b):
    return a.x * b.x + a.y * b.y


def cross(a, b):
    return a.x * b.y - a.y * b.x


def ccw(p0, p1, p2):
    COUNTER_CLOCKWISE = 1
    CLOCKWISE = -1
    ONLINE_BACK = 2
    ONLINE_FRONT = -2
    ON_SEGMENT = 0
    a = p1 - p0
    b = p2 - p0
    if cross(a, b) > EPS:
        return COUNTER_CLOCKWISE
    if cross(a, b) < -EPS:
        return CLOCKWISE
    if dot(a, b) < -EPS:
        return ONLINE_BACK
    if a.norm() < b.norm():
        return ONLINE_FRONT
    return ON_SEGMENT


def intersect(s1, s2):
    p1 = s1.p1
    p2 = s1.p2
    p3 = s2.p1
    p4 = s2.p2
    return (ccw(p1, p2, p3) * ccw(p1, p2, p4) <= 0 and
            ccw(p3, p4, p1) * ccw(p3, p4, p2) <= 0)


if __name__ == '__main__':
    q = int(input())
    ans = []
    for i in range(q):
        x0, y0, x1, y1, x2, y2, x3, y3 = [int(v) for v in input().split()]
        s1 = Segment(Point(x0, y0), Point(x1, y1))
        s2 = Segment(Point(x2, y2), Point(x3, y3))
        ans.append(intersect(s1, s2))

    for v in ans:
        print(int(v))

Submission status: Runtime Error

Solution code:
class Line:
    def __init__(self,p1,p2):
        if p1[1] < p2[1]:self.s=p2;self.e=p1
        elif p1[1] > p2[1]:self.s=p1;self.e=p2
        else:
            if p1[0] < p2[0]:self.s=p1;self.e=p2
            else:self.s=p2;self.e=p1
def dot(a,b):return a[0]*b[0] + a[1]*b[1]
def cross(a,b):return a[0]*b[1] - a[1]*b[0]
def dif(a,b):return [x-y for x,y in zip(a,b)]
def InterSection(l,m):
    a = dif(l.e,l.s);b = dif(m.e,l.s);c = dif(m.s,l.s)
    d = dif(m.e,m.s);e = dif(l.e,m.s);f = dif(l.s,m.s)
    g = lambda a, b : cross(a,b)==0 and dot(a,b)>0 and dot(b,b)<dot(a,a)
    if g(a,b) or g(a,c) or g(d,e) or g(d,f):return True
    elif l.s == m.e or l.s == m.s or l.e == m.e or l.e == m.s:return True
    elif cross(a,b) * cross(a,c) >= 0 or cross(d,e) * cross(d,f) >= 0:return False
    else:return True

q = int(input())
for i in range(q):
    x0,y0,x1,y1,x2,y2,x3,y3 = [int(i) for i in input().split()]
    a = [x0,y0] ; b = [x1,y1] ; c = [x2,y2] ; d = [x3,y3]
    l1 = Line(b,1) ; l2 = Line(b,1)
    if InterSection(l1,l2):print(1)
    else:print(0)

Submission status: Runtime Error

Solution code:
import math

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

class Segment():
    def __init__(self, x1, y1, x2, y2):
        self.p1 = Point(x1, y1)
        self.p2 = Point(x2, y2)
        self.slope = None
        self.intersept = None
        if self.p1.x == self.p2.x:
            self.slope = float('inf')
        else:
            self.slope = (self.p2.y - self.p1.y)/(self.p2.x - self.p1.x)
            self.intersept = self.p1.y - self.slope*self.p1.x

    def is_in_range(self, x, y):
        return ((x - self.p1.x)*(x - self.p2.x) <= 0 and (y - self.p1.y)*(y - self.p2.y) <= 0)

    def is_intersect(self, seg):
        if self.slope == seg.slope: return False
        slope_diff = seg.slope - self.slope
        if self.slope == float('inf'):
            x = self.p1.x
        elif seg.slope == float('inf'):
            x = seg.p1.x
        else:
            x = -(seg.intersept - self.intersept)/slope_diff
        y = self.slope * x + self.intersept
        if seg.is_in_range(x, y) and self.is_in_range(x, y): return True
        return False


q = int(input())
for i in range(q):
    x0, y0, x1, y1, x2, y2, x3, y3 = list(map(int, input().split(' ')))
    line1, line2 = Segment(x0, y0, x1, y1), Segment(x2, y2, x3, y3)
    if line1.is_intersect(line2):
        print(1)
    else:
        print(0)