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
... q th query Each query consists of integer coordinates of end points of s1 and s2 in the following format:  x p0  y p0  x p1  y p1  x p2  y p2  x p3  y p3  Output For each query, print "1" or "0". Constraints  1 ≤ q ≤ 1000  -10000 ≤ x p i , y p i ≤ 10000   p0 ≠ p1 and p2 ≠ 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

Solution (Python):
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)


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 
        if sgn((a-b).dot(c-b)) < 0: return  2 
        return 0 


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 


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


def Intersection(a,b,c,d):
    tmp1 = (b-a)*((c-a).det(d-c))
    tmp2 = (b-a).det(d-c)
    return a+(tmp1/tmp2)


def DistanceLineToPoint(a,b,c):
    return abs(((c-a).det(b-a))/((b-a).abs()))


def DistanceSeglineToPoint(a,b,c):
    if sgn((b-a).dot(c-a)) < 0: 
        return (c-a).abs()
    if sgn((a-b).dot(c-b)) < 0: 
        return (c-b).abs()
    return DistanceLineToPoint(a,b,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)) 
    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)

Solution (Python):
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)

Solution (Python):
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の交差判定
    '''
    
    
    
    
    
    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")

Solution (Python):


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):
            
            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):
            
            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()

Solution (Python):
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)

Solution (Python):



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

Solution (Python):
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   
        elif cross < 0:
            return 1    
        else:           
            dot = self.dot(vec_pt1_to_pt)
            if dot < 0:
                return -2    
            else:       
                if self.abs() < vec_pt1_to_pt.abs():
                    return 2    
                else:
                    return 0    

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

Solution (Python):
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)))

Solution (Python):
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))