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:
# -*- coding: utf-8 -*-
"""
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=CGL_2_B&lang=jp

"""
import sys
from sys import stdin
input = stdin.readline


class Point(object):
    epsilon = 1e-10

    def __init__(self, x=0.0, y=0.0):
        if isinstance(x, tuple):
            self.x = x[0]
            self.y = x[1]
        else:
            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):
        return Point(other * self.x, other * self.y)

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

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

    def __eq__(self, other):
        from math import fabs
        if fabs(self.x - other.x) < Point.epsilon and fabs(self.y - other.y) < Point.epsilon:
            return True
        else:
            return False

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

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


class Vector(Point):
    def __init__(self, x=0.0, y=0.0):
        if isinstance(x, tuple):
            self.x = x[0]
            self.y = x[1]
        elif isinstance(x, Point):
            self.x = x.x
            self.y = x.y
        else:
            self.x = x
            self.y = y

    # ????????????
    def __add__(self, other):
        return Vector(self.x + other.x, self.y + other.y)

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

    def __mul__(self, other):
        return Vector(other * self.x, other * self.y)

    def __truediv__(self, other):
        return Vector(other / self.x, other / self.y)

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

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

    @classmethod
    def is_orthogonal(cls, a, b):
        return Vector.dot(a, b) == 0.0

    @classmethod
    def is_parallel(cls, a, b):
        return Vector.cross(a, b) == 0.0


class Segment(object):
    def __init__(self, p1=Point(), p2=Point()):
        if isinstance(p1, Point):
            self.p1 = p1
            self.p2 = p2
        elif isinstance(p1, tuple):
            self.p1 = Point(p1[0], p1[1])
            self.p2 = Point(p2[0], p2[1])

    @classmethod
    def is_orthogonal(cls, s1, s2):
        a = Vector(s1.p2 - s1.p1)
        b = Vector(s2.p2 - s2.p1)
        return Vector.is_orthogonal(a, b)

    @classmethod
    def is_parallel(cls, s1, s2):
        a = Vector(s1.p2 - s1.p1)
        b = Vector(s2.p2 - s2.p1)
        return Vector.is_parallel(a, b)


class Line(Segment):
    pass


class Cirle(object):
    def __init__(self, c=Point(), r=0.0):
        self.c = c
        self.r = r


def ccw(p0, p1, p2):
    a = Vector(p1 - p0)
    b = Vector(p2 - p0)
    epsilon = 1e-10
    if Vector.cross(a, b) > epsilon:
        return 1 # 'COUNTER_CLOCKWISE'
    elif Vector.cross(a, b) < -epsilon:
        return -1 # 'CLOCKWISE'
    elif Vector.dot(a, b) < -epsilon:
        return 2 # 'ONLINE_BACK'
    elif a.norm() < b.norm():
        return -2 # 'ONLINE_FRONT'
    else:
        return 0 # 'ON_SEGMENT'


def intersect(p0, p1, p2=Point(), p3=Point()):
    if isinstance(p0, Point):
        ans1 = ccw(p0, p1, p2) * ccw(p0, p1, p3)
        ans2 = ccw(p2, p3, p0) * ccw(p2, p3, p1)
        return ans1 <= 0 and ans2 <= 0
    elif isinstance(p0, Segment):
        ans1 = ccw(p0.p1, p0.p2, p1.p1) * ccw(p0.p1, p0.p2, p1.p2)
        ans2 = ccw(p1.p1, p1.p2, p0.p1) * ccw(p1.p1, p1.p2, p0.p2)
        return ans1 <= 0 and ans2 <= 0


def main(args):
    q = int(input())
    for _ in range(q):
        x_p0, y_p0, x_p1, y_p1, x_p2, y_p2, x_p3, y_p3 = map(int, input().split())
        p0 = Point(x_p0, y_p0)
        p1 = Point(x_p1, y_p1)
        p2 = Point(x_p2, y_p2)
        p3 = Point(x_p3, y_p3)
        #result = intersect(p0, p1, p2, p3)

        s1 = Segment(p0, p1)
        s2 = Segment(p2, p3)
        result = intersect(s1, s2)
        print(int(result))


if __name__ == '__main__':
    main(sys.argv[1:])

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""


"""
import sys
from sys import stdin
input = stdin.readline


class Point(object):
    epsilon = 1e-10

    def __init__(self, x=0.0, y=0.0):
        if isinstance(x, tuple):
            self.x = x[0]
            self.y = x[1]
        else:
            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):
        return Point(other * self.x, other * self.y)

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

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

    def __eq__(self, other):
        from math import fabs
        if fabs(self.x - other.x) < Point.epsilon and fabs(self.y - other.y) < Point.epsilon:
            return True
        else:
            return False

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

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

    def ccw(self, p0, p1):
        # ??????2???(p0, p1)?????????????????????????????????????????¢????????????
        a = Vector(p1 - p0)
        b = Vector(self - p0)
        if Vector.cross(a, b) > Point.epsilon:
            return 1 # 'COUNTER_CLOCKWISE'
        elif Vector.cross(a, b) < -Point.epsilon:
            return -1 # 'CLOCKWISE'
        elif Vector.dot(a, b) < -Point.epsilon:
            return 2 # 'ONLINE_BACK'
        elif a.norm() < b.norm():
            return -2 # 'ONLINE_FRONT'
        else:
            return 0 # 'ON_SEGMENT'

    def project(self, s):
        # ??????(Point)????????????s??????????????????????????????????????§?¨?(?°???±)????±???????
        base = Vector(s.p2 - s.p1)
        a = Vector(self - s.p1)
        r = Vector.dot(a, base)
        r /= base.norm()
        return s.p1 + base * r

    def reflect(self, s):
        # ??????s???????§°?????¨?????????????????¨???????§°??????????????§?¨?(????°?)????±???????
        proj = self.project(s)
        return self + (proj - self)*2


class Vector(Point):
    def __init__(self, x=0.0, y=0.0):
        if isinstance(x, tuple):
            self.x = x[0]
            self.y = x[1]
        elif isinstance(x, Point):
            self.x = x.x
            self.y = x.y
        else:
            self.x = x
            self.y = y

    # ????????????
    def __add__(self, other):
        return Vector(self.x + other.x, self.y + other.y)

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

    def __mul__(self, other):
        return Vector(other * self.x, other * self.y)

    def __truediv__(self, other):
        return Vector(other / self.x, other / self.y)

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

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

    @classmethod
    def is_orthogonal(cls, a, b):
        return Vector.dot(a, b) == 0.0

    @classmethod
    def is_parallel(cls, a, b):
        return Vector.cross(a, b) == 0.0


class Segment(object):
    def __init__(self, p1=Point(), p2=Point()):
        if isinstance(p1, Point):
            self.p1 = p1
            self.p2 = p2
        elif isinstance(p1, tuple):
            self.p1 = Point(p1[0], p1[1])
            self.p2 = Point(p2[0], p2[1])

    def intersect(self, s):
        # ????????¨??????????????????????????????????????????????????????
        ans1 = s.p1.ccw(self.p1, self.p2) * s.p2.ccw(self.p1, self.p2)
        ans2 = self.p1.ccw(s.p1, s.p2) * self.p2.ccw(s.p1, s.p2)
        return ans1 <= 0 and ans2 <= 0

    @classmethod
    def is_orthogonal(cls, s1, s2):
        a = Vector(s1.p2 - s1.p1)
        b = Vector(s2.p2 - s2.p1)
        return Vector.is_orthogonal(a, b)

    @classmethod
    def is_parallel(cls, s1, s2):
        a = Vector(s1.p2 - s1.p1)
        b = Vector(s2.p2 - s2.p1)
        return Vector.is_parallel(a, b)


class Line(Segment):
    pass


class Cirle(object):
    def __init__(self, c=Point(), r=0.0):
        self.c = c
        self.r = r



def cross_point(s1, s2):
    base = s2.p2 - s2.p1
    d1 = abs(Vector.cross(base, s1.p1-s2.p1))
    d2 = abs(Vector.cross(base, s1.p2-s2.p1))
    t = d1 / (d1 + d2)
    return s1.p1 + (s1.p2 - s1.p1) * t


def main(args):
    q = int(input())
    for _ in range(q):
        x_p0, y_p0, x_p1, y_p1, x_p2, y_p2, x_p3, y_p3 = map(int, input().split())
        p0 = Point(x_p0, y_p0)
        p1 = Point(x_p1, y_p1)
        p2 = Point(x_p2, y_p2)
        p3 = Point(x_p3, y_p3)
        s1 = Segment(p0, p1)
        s2 = Segment(p2, p3)
        result = s1.intersect(s2)
        print(int(result))



if __name__ == '__main__':
    main(sys.argv[1:])

Submission status: Accepted

Solution code:
from math import sqrt
q = int(input())

def norm(a):
    return sqrt(a[0] ** 2 + a[1] ** 2)

def dot(a, b):
    return sum([i * j for i,j in zip(a, b)])

def sub(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 ccw(a, b, c):
    x = sub(b, a)
    y = sub(c, a)
    if cross(x, y) > 0: return 1
    if cross(x, y) < 0: return -1
    if dot(x, y) < 0: return 2
    if norm(x) < norm(y): return -2
    return 0

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

for i in range(q):
    xp0, yp0, xp1, yp1, xp2, yp2, xp3, yp3 = map(int, input().split())
    print(1 if intersect([xp0, yp0], [xp1, yp1], [xp2, yp2], [xp3, yp3]) else 0)

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:
# -*- coding: utf-8 -*-

import collections
import math


class Vector2(collections.namedtuple("Vector2", ["x",  "y"])):

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

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

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

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

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

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

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

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


def getDistanceSP(segment, point):
    p = point
    p1, p2 = segment
    if (p2 - p1).dot(p - p1) < 0:
        return abs(p - p1)
    if (p1 - p2).dot(p - p2) < 0:
        return abs(p - p2)
    return abs((p2 - p1).cross(p - p1)) / abs(p2 - p1)


def getDistance(s1, s2):
    a, b = s1
    c, d = s2
    if intersect(s1, s2):  # intersect
        return 0
    return min(getDistanceSP(s1, c), getDistanceSP(s1, d), getDistanceSP(s2, a), getDistanceSP(s2, b))


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


def intersect(s1, s2):
    a, b = s1
    c, d = s2
    return ccw(a, b, c) * ccw(a, b, d) <= 0 and ccw(c, d, a) * ccw(c, d, b) <= 0


if __name__ == '__main__':

    n = int(input())

    for _ in range(n):
        l = list(map(int, input().split()))
        s1 = [Vector2(l[0], l[1]), Vector2(l[2], l[3])]
        s2 = [Vector2(l[4], l[5]), Vector2(l[6], l[7])]

        print(int(intersect(s1, s2)))

Submission status: Accepted

Solution code:
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
        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)

    def is_intersect(self, seg):
        a = (seg.p1.x - seg.p2.x) * (self.p1.y - seg.p1.y) + (seg.p1.y - seg.p2.y) * (seg.p1.x - self.p1.x)
        b = (seg.p1.x - seg.p2.x) * (self.p2.y - seg.p1.y) + (seg.p1.y - seg.p2.y) * (seg.p1.x - self.p2.x)
        c = (self.p1.x - self.p2.x) * (seg.p1.y - self.p1.y) + (self.p1.y - self.p2.y) * (self.p1.x - seg.p1.x)
        d = (self.p1.x - self.p2.x) * (seg.p2.y - self.p1.y) + (self.p1.y - self.p2.y) * (self.p1.x - seg.p2.x)
        e = (self.p1.x - seg.p1.x)*(self.p2.x - seg.p2.x)
        f = (self.p1.x - seg.p2.x)*(self.p2.x - seg.p1.x)
        g = (self.p1.y - seg.p1.y)*(self.p2.y - seg.p2.y)
        h = (self.p1.y - seg.p2.y)*(self.p2.y - seg.p1.y)
        return a*b <= 0 and c*d <= 0 and (e <= 0 or f <= 0) and (g <= 0 or h <= 0)

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)

Submission status: Accepted

Solution code:
import math
EPS=1e-10

#点类
class Point():

    def __init__(self,x,y):
        self.x=x
        self.y=y
    
    def __sub__(self,p):
        return Point(self.x - p.x, self.y - p.y);
    def __add__(self,p):
        return Point(self.x + p.x, self.y + p.y)
           
    def __mul__(self,a): #a: scalar
        return Point(self.x * a, self.y * a)
    def __truediv__(self,a): #a: scalar
        return Point(self.x / a, self.y / a)
   
    def __str__(self):
       return  str(self.x)+','+str(self.y)
    def __repr__(self):
        return  'Point('+str(self.x)+','+str(self.y)+')'
    
    def __lt__(self, other):    
        if self.y-other.y==0:
            return self.x<other.x
        else:
            return self.y<other.y
            
    def __eq__(self, other):    
        return abs(self.x-other.x)<EPS and  abs(self.y-other.y)<EPS


# 线段类
class Segment():
    def __init__(self,p1, p2):
        self.p1=p1
        self.p2=p2
    def __str__(self):
        return  'segment:('+str(self.p1)+';'+str(self.p2)+')'
    def __repr__(self):
        return  'segment:('+str(self.p1)+';'+str(self.p2)+')'


class Circle():
    def __init__(self,c, r):
        self.c=c
        self.r=r

    def __str__(self):
       return  'Circle:(center point: '+str(self.c)+'; radius: '+str(self.r)+')'
    def __repr__(self):
       return  'Circle:(center point: '+str(self.c)+'; radius: '+str(self.r)+')'
   
    
#定义多边形
class Polygon():
    def __init__(self,ps=[]):
        self.ps=ps
        self.size=len(ps)
  
    def __getitem__(self, i):#iter override 
        return self.ps[i]  
    def __setitem__(self,i,p): 
        self.ps[i]=p               
    def __iter__(self):     
        return self.ps  
    
    def addpoint(self,i,p):
        self.ps.insert(i,p)
        self.size+=1
    def delpoint(self,i):
        self.size-=1
        return self.ps.pop(i)
    def sortYX(self):
        self.ps.sort()
        #self.ps.sort(key=attrgetter('y','x'))
    def __str__(self):
       return  'Polygon:'+str(tuple(self.ps))
    def __repr__(self):
       return  'Polygon:'+str(tuple(self.ps))
        
    def __len__(self):
        return len(self.ps)
    def __eq__(self, other):  
         return self.ps==other.ps
    
    def draw(self):
      
       turtle.screensize(800,800,"black")
       #turtle.setup(width=0.9,height=0.9)
       turtle.title("Polygon convex hull")
       turtle.setworldcoordinates(-400,-400,400,400) 

       #print(turtle.screensize())
       #mywin = turtle.Screen()    
       #mywin.   
       t=turtle.Turtle() 
       #mywin=turtle.Screen()
       
       t.pencolor("red")
       for pt in self.ps:
           t.goto(pt.x,pt.y)
           t.dot(10,'white')
       
 

#***************************点、向量****************************

#向量的模的平方
def norm(p):  
    return p.x * p.x + p.y * p.y


#向量P的长度
def length(p):
    return math.sqrt(p.x * p.x + p.y * p.y)


# 向量的(点)内积, dot(a,b)=|a|*|b|*cos(a,b) (从a,到b的角)
# =============================================================================
# r=dot(a,b),得到矢量a和b的点积，如果两个矢量都非零矢量  
# r<0：两矢量夹角为钝角； 
# r=0：两矢量夹角为直角； 
# r>0：两矢量夹角为锐角  
# =============================================================================
def dot(a, b) :
    return a.x * b.x + a.y * b.y



# =============================================================================
# # 向量的（叉）外积 cross(a,b)=|a||b|*sin(a,b) (从a,到b的角)由a,b构成的平行四边的面积
# r=cross(a,b),得到向量a和向量b的叉积  
# r>0：b在矢量a的逆时针方向；  
# r=0：a,b 平行共线；  
# r<0：b在向量a的顺时针方向 
# =============================================================================
def cross( a, b) :
    return a.x * b.y - a.y * b.x

# 点p在线段s上的投影
def project(s, p):
    base = s.p2 - s.p1
    r = dot(p - s.p1, base) / norm(base)
    return s.p1 + base * r 


# 点a到点b的距离
def getDistance(a, b) :
    return length(a - b)

# 线段l和点p的距离
def getDistanceLP(l, p) :
    return abs( cross(l.p2 - l.p1, p - l.p1) / length(l.p2 - l.p1) )

#getDistanceLP(s3, p7)
    
#线段s与点p的距离
def getDistanceSP(s, p) :
    if (dot(s.p2 - s.p1, p - s.p1) < 0.0):
        return length(p - s.p1)
    if (dot(s.p1 - s.p2, p - s.p2) < 0.0):
        return length(p - s.p2)
    return getDistanceLP(s, p)

#print(getDistanceLP(s3, Point(5,5)))
#print(getDistanceSP(s3, Point(5,5)))


#*************************线段********************************/
# 线段s1，s2是否正交 <==> 内积为0
def isOrthogonalSG(s1, s2) :
    return abs(dot(s1.p2 - s1.p1, s2.p2 - s2.p1))<EPS


# 线段s1，s2是否平行 <==> 叉积为0
def isParallelLN(s1,s2) :
    return abs(cross(s1.p2 - s1.p1, s2.p2 - s2.p1))<0




# 逆时针方向ccw（Counter-Clockwise）
COUNTER_CLOCKWISE = 1;
CLOCKWISE = -1;
ONLINE_BACK = -2;
ONLINE_FRONT = 2;
ON_SEGMENT = 0;

def ccw(p0, p1, p2) :
    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 (norm(a) < norm(b)):
        return ONLINE_FRONT
    
    return ON_SEGMENT;


def toleft(p0,p1,p2):
    a = p1 - p0
    b = p2 - p0  
    tmp=cross(a,b)
    if tmp > EPS:
        return 1
    elif abs(tmp)<EPS and norm(a)<=norm(b):
        return 2  #共线，p2在p0p1的右延长线上
    elif abs(tmp)<EPS and norm(a)>norm(b):
        return -2  #共线，p2在p0p1的left延长线上    
    else:
        return -1


#以线段s为对称轴与点p成线对称的点
def reflect(s, p) :
    return p + (project(s, p) - p) * 2.0



#判断线段s1和s2是否相交
def intersectSG(s1, s2) :
    return intersectP4(s1.p1, s1.p2, s2.p1, s2.p2)


# 线段s1和线段s2的距离
def getDistanceSG(s1, s2) :
    # 相交
    if (intersectSG(s1, s2)):
        return 0.0
    return min(getDistanceSP(s1, s2.p1), getDistanceSP(s1, s2.p2),\
        getDistanceSP(s2, s1.p1), getDistanceSP(s2, s1.p2))

# 判断线段p1p2和线段p3p4是否相交
def intersectP4(p1, p2, p3, p4) :
    return ccw(p1, p2, p3) * ccw(p1, p2, p4) <= 0 and \
            ccw(p3, p4, p1) * ccw(p3, p4, p2) <= 0





q=int(input())
for i in range(0,q):
    s= [int(x) for x in input().split()]
    p0=Point(s[0],s[1])
    p1=Point(s[2],s[3])
    p2=Point(s[4],s[5])
    p3=Point(s[6],s[7])
    
    
    if p0==p2 or p0==p3 or p1==p2 or p1==p3:
        print(1)

    elif cross(p1-p0,p2-p0)*cross(p1-p0,p3-p0)<0 and \
           cross(p3-p2,p0-p2)*cross(p3-p2,p1-p2)<0:
       print(1)
    
    elif cross(p1-p0,p2-p0)==0 and dot (p1-p0,p2-p0)>0 and \
            length(p2-p0)<length(p1-p0):
        print(1)
                
    elif cross(p1-p0,p3-p0)==0 and dot (p1-p0,p3-p0)>0 and \
            length(p3-p0)<length(p3-p0):
        print(1)


    elif cross(p3-p2,p0-p2)==0 and dot (p3-p2,p0-p2)>0 and \
            length(p0-p2)<length(p3-p2):
        print(1)
                
    elif cross(p3-p2,p1-p2)==0 and dot (p3-p2,p1-p2)>0 and \
            length(p1-p2)<length(p3-p2):
        print(1)

    else:
       print(0)

Submission status: Accepted

Solution code:
import math

class Vector:
    def __init__(self,x,y):
        self.x = x
        self.y = y
        
    def __add__(self,other):
        return Vector(self.x+other.x,self.y+other.y)
    
    def __sub__(self,other):
        return Vector(self.x-other.x,self.y-other.y)
    
    def __mul__(self,scalar):
        return Vector(self.x*scalar,self.y*scalar)
    def __rmul__(self, scalar):
        return Vector(self.x*scalar,self.y*scalar)
   
    def __repr__(self):
        return str([self.x,self.y])
        
    def norm_2(self):
        return dot(self,self)
    
    def norm(self):
        return math.sqrt(self.norm_2())
    
def v_sum(v1,v2):
    return Vector(v1.x+v2.x,v1.y+v2.y) 
def scalar_multi(k,v):
    return Vector(k*v.x,k*v.y)
def v_diff(v1,v2):
    return v_sum(v1,scalar_multi(-1,v2))
    
def dot(vector1,vector2):
    return vector1.x*vector2.x+vector1.y*vector2.y

def cross(vector1,vector2):
    return vector1.x*vector2.y-vector1.y*vector2.x

def is_crossed(p,q,s,t):
    a = q-p
    b = t-s
    v = s-p
    w = t-p
    x = p-s
    y = q-s
    if cross(a,v)*cross(a,w)<=0 and cross(b,x)*cross(b,y)<=0:
        if cross(a,v) == cross(a,w) == cross(b,x) == cross(b,y) == 0:
            if 0<=dot(a,v)<=a.norm_2() or 0<=dot(a,w)<=a.norm_2()  or 0<=dot(b,x)<=b.norm_2() or 0<=dot(b,y)<=b.norm_2():
                return True
            else:
                return False
        else:    
            return True
    else:
        return False
        
q = int(input())
for i in range(q):
    x1,y1,x2,y2,x3,y3,x4,y4 = map(int,input().split())
    p1 = Vector(x1,y1)
    p2 = Vector(x2,y2)
    p3 = Vector(x3,y3)
    p4 = Vector(x4,y4)
    
    if is_crossed(p1,p2,p3,p4):
        print(1)
    else:
        print(0)

Submission status: Accepted

Solution code:
EPS = 10**(-9)
def is_equal(a,b):
    return abs(a-b) < EPS

def norm(v,i=2):
    import math
    ret = 0
    n = len(v)
    for j in range(n):
        ret += abs(v[j])**i
    return math.pow(ret,1/i)

class Vector(list):
    """
    ベクトルクラス
    対応演算子
    +  : ベクトル和 
    -  : ベクトル差
    *  : スカラー倍、または内積
    /  : スカラー除法
    ** : 外積
    += : ベクトル和
    -= : ベクトル差
    *= : スカラー倍
    /= : スカラー除法

    メソッド
    self.norm(i) : L{i}ノルムを計算
    """
    def __add__(self,other):
        n = len(self)
        ret = [0]*n
        for i in range(n):
            ret[i] = super().__getitem__(i) + other.__getitem__(i)
        return self.__class__(ret)
    
    def __radd__(self,other):
        n = len(self)
        ret = [0]*n
        for i in range(n):
            ret[i] = other.__getitem__(i) + super().__getitem__(i)
        return self.__class__(ret)
    
    def __iadd__(self, other):
        n = len(self)
        for i in range(n):
            self[i] += other.__getitem__(i)
        return self

    def __sub__(self,others):
        n = len(self) 
        ret = [0]*n
        for i in range(n):
            ret[i] = super().__getitem__(i) - others.__getitem__(i)
        return self.__class__(ret)

    def __iadd__(self, other):
        n = len(self)
        for i in range(n):
            self[i] -= other.__getitem__(i)
        return self

    def __rsub__(self,others):
        n = len(self) 
        ret = [0]*n
        for i in range(n):
            ret[i] = others.__getitem__(i) - super().__getitem__(i)
        return self.__class__(ret)
    
    def __mul__(self,other):
        n = len(self)
        if isinstance(other,list):
            ret = 0
            for i in range(n):
                ret += super().__getitem__(i)*other.__getitem__(i)
            return ret
        else:
            ret = [0]*n
            for i in range(n):
                ret[i] = super().__getitem__(i)*other
            return self.__class__(ret)

    def __rmul__(self,other):
        n = len(self)
        if isinstance(other,list):
            ret = 0
            for i in range(n):
                ret += super().__getitem__(i)*other.__getitem__(i)
            return ret
        else:
            ret = [0]*n
            for i in range(n):
                ret[i] = super().__getitem__(i)*other
            return self.__class__(ret)
    
    
    def __truediv__(self,other):
        """
        ベクトルのスカラー除法
        Vector/scalar
        """
        n = len(self)
        ret = [0]*n
        for i in range(n):
            ret[i] = super().__getitem__(i)/other
        return self.__class__(ret)
    
    def norm(self,i):
        """
        L{i}ノルム
        self.norm(i)
        """
        return norm(self,i)
    
    def __pow__(self,other):
        """
        外積
        self**other
        """
        n = len(self)
        ret = [0]*3
        x = self[:]
        y = other[:]
        if n == 2:
            x.append(0)
            y.append(0)
        if n == 2 or n == 3:
            for i in range(3):
                ret[0],ret[1],ret[2] = x[1]*y[2]-x[2]*y[1],x[2]*y[0]-x[0]*y[2],x[0]*y[1]-x[1]*y[0]
            ret = Vector(ret)
            if n == 2:
                return ret
            else:
                return ret

class Segment:
    """
    線分クラス
    """
    def __init__(self,v1,v2):
        self.v1 = v1
        self.v2 = v2
    
    def length(self):
        return norm(self.v1-self.v2)

    def get_unit_vec(self):
        #方向単位ベクトル
        dist = norm(self.v2-self.v1)
        if dist != 0:
            return (self.v2-self.v1)/dist
        else:
            return False
    
    def projection(self,vector):
        #射影点(線分を直線と見たときの)
        unit_vec = self.get_unit_vec()
        t = unit_vec*(vector-self.v1)
        return self.v1 + t*unit_vec
    
    def is_vertical(self,other):
        #線分の直交判定
        return is_equal(0,self.get_unit_vec()*other.get_unit_vec())
    
    def is_horizontal(self,other):
        #線分の平行判定
        return is_equal(0,self.get_unit_vec()**other.get_unit_vec())
    
    def reflection(self,vector):
        #反射点(線分を直線と見たときの)
        projection = self.projection(vector)
        v = projection - vector
        return projection + vector
    
    def include(self,vector):
        #線分が点を含むか否か
        proj = self.projection(vector)
        if not is_equal(norm(proj-vector),0):
            return False
        else:
            n = len(self.v1)
            f = True
            for i in range(n):
                f &= ((self.v1[i] <= vector[i] <= self.v2[i]) or (self.v2[i] <= vector[i] <=self.v1[i]))
            return f
    
    def distance(self,other):
        #点と線分の距離
        if isinstance(other,Vector):
            proj = self.projection(other)
            if self.include(proj):
                return norm(proj-other)
                ret = []
                ret.append(norm(self.v1-other))
                ret.append(norm(self.v2-other))
                return min(ret)

    def ccw(self,vector):
        """
        線分に対して点が反時計回りの位置にある(1)か時計回りの位置にある(-1)か線分上にある(0)か
        """
        direction = self.v2 - self.v1
        v = vector - self.v1
        if self.include(vector):
            return 0
        else:
            cross = direction**v
            if cross[2] <= 0:
                return 1
            else:
                return -1
    
    def intersect(self,segment):
        ccw12 = self.ccw(segment.v1)
        ccw13 = self.ccw(segment.v2)
        ccw20 = segment.ccw(self.v1)
        ccw21 = segment.ccw(self.v2)

        if ccw12*ccw13*ccw20*ccw21 == 0:
            return True
        else:
            if ccw12*ccw13 < 0 and ccw20*ccw21 < 0:
                return True
            else:
                return False







class Line(Segment):
    """
    直線クラス
    """
    #直線上に点が存在するか否か
    def include(self,vector):
        proj = self.projection(vector)
        return is_equal(norm(proj-vector),0)


q = int(input())
P0s,P1s,P2s,P3s = [0]*q,[0]*q,[0]*q,[0]*q
for i in range(q):
    tmp = list(map(int, input().split()))
    P0s[i],P1s[i],P2s[i],P3s[i] = Vector(tmp[0:2]),Vector(tmp[2:4]),Vector(tmp[4:6]),Vector(tmp[6:8])

for i in range(q):
    p0,p1,p2,p3 = P0s[i],P1s[i],P2s[i],P3s[i]
    S1 = Segment(p0,p1)
    S2 = Segment(p2,p3)

    if S1.intersect(S2):
        print(1)
    else:
        print(0)