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


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):  
        return math.sqrt(float(self.x * self.x + self.y * self.y))

    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 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):  
        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  
    elif a.cross(b) < 0:
        return -1  
    elif a.dot(b) < 0:
        return 2  
    elif abs(a) < abs(b):
        return -2  
    else:
        return 0  


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

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

Solution (Python):
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): 
        return Point(self.x * a, self.y * a)
    def __truediv__(self,a): 
        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):
        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()
        
    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.title("Polygon convex hull")
       turtle.setworldcoordinates(-400,-400,400,400) 

       
       
       
       t=turtle.Turtle() 
       
       
       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



def length(p):
    return math.sqrt(p.x * p.x + p.y * p.y)









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 project(s, p):
    base = s.p2 - s.p1
    r = dot(p - s.p1, base) / norm(base)
    return s.p1 + base * r 



def getDistance(a, b) :
    return length(a - b)


def getDistanceLP(l, p) :
    return abs( cross(l.p2 - l.p1, p - l.p1) / length(l.p2 - l.p1) )


    

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)







def isOrthogonalSG(s1, s2) :
    return abs(dot(s1.p2 - s1.p1, s2.p2 - s2.p1))<EPS



def isParallelLN(s1,s2) :
    return abs(cross(s1.p2 - s1.p1, s2.p2 - s2.p1))<0





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  
    elif abs(tmp)<EPS and norm(a)>norm(b):
        return -2  
    else:
        return -1



def reflect(s, p) :
    return p + (project(s, p) - p) * 2.0




def intersectSG(s1, s2) :
    return intersectP4(s1.p1, s1.p2, s2.p1, s2.p2)



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


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)

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

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

Solution (Python):
import math

class Point:
    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):
        return Point(self.x * other, self.y * other)
    def __floordiv__(self, other):
        return Point(self.x / other, self.y / other)
    def __repr__(self):
        return str(self.x) + ' ' + str(self.y)

class Vector(Point):
    pass

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

class Segment(Line):
    pass

def points_to_vector(p1, p2):
    x = p1.x - p2.x
    y = p1.y - p2.y
    return Vector(x, y)

def vector(p):
    return Vector(p.x, p.y)

def dot(v1, v2):
    return v1.x * v2.x + v1.y * v2.y

def cross(v1, v2):
    return v1.x * v2.y - v1.y * v2.x

def norm(v):
    return v.x**2 + v.y**2

def distance(v):
    return math.sqrt(norm(v))

def project(s, p):
    base = points_to_vector(s.p1, s.p2)
    hypo = points_to_vector(p, s.p1)
    r = dot(hypo, base) / norm(base)
    return s.p1 + base * r

def reflect(s, p):
    return p + (project(s, p) -p) * 2











def get_distance_pp(p1, p2):
    return distance(p1 - p2)

def get_distance_lp(l, p):
    return distance(cross(l.p2 - l.p1, p - l.p1)) / distance(l.p2 - l.p1)

def get_distance_sp(s, p):
    if dot(s.p2 - s.p1, p - s.p1) < 0:
        return distance(p - s.p1)
    elif dot(s.p1 - s.p2, p - s.p2) < 0:
        return distance(p - s.p2)
    else:
        return get_distance_lp(s, p)

def ccw(p0, p1, p2):
    EPS = 1e-10
    COUNTER_CLOCKWISE = 1
    CLOCKWISE = -1
    ONLINE_BACK = 2
    ONLINE_FRONT = -2
    ON_SEGMENT = 0
    v1 = p1 - p0
    v2 = p2 - p0
    if cross(v1, v2) > EPS:
        return COUNTER_CLOCKWISE
    elif cross(v1, v2) < -EPS:
        return CLOCKWISE
    elif dot(v1, v2) < -EPS:
        return ONLINE_BACK
    elif norm(v1) < norm(v2):
        return ONLINE_FRONT
    else:
        return ON_SEGMENT

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

def intersect_s(s1, s2):
    return intersect_p(s1.p1, s1.p2, s2.p1, s2.p2)


import sys


q = int(input())
for i in range(q):
    temp = list(map(int, input().split()))
    points = []
    for j in range(0, 8, 2):
        points.append(Point(temp[j], temp[j+1]))
    s1 = Segment(points[0], points[1])
    s2 = Segment(points[2], points[3])
    if intersect_s(s1, s2):
        print(1)
    else:
        print(0)

Solution (Python):
import math

EPS = 1e-10

COUNTER_CLOCKWISE = 1
CLOCKWISE = -1
ONLINE_BACK = 2
ONLINE_FRONT = -2
ON_SEGMENT = 0

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

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

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

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

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

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

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

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

    def __eq__(self, point):
        
        return abs(self.x-point.x) < EPS and abs(self.y-point.y) <EPS

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 isOrthogonal(a, b):
    return dot(a, b) == 0

def isParallel(a, b):
    return cross(a, b) == 0

def project(s, p):
    
    base = s.p2 - s.p1
    r = dot(p-s.p1, base)/base.norm()
    return s.p1+base*r

def reflect(s, p):
    return p+(project(s, p)-p)*2

def get_distance(a, b):
    return abs(a-b)

def get_distance_lp(l, p):
    return abs(cross(l.p2-l.p1, p-l.p1)/abs(l.p2-l.p1))

def get_distance_sp(s, p):
    if dot(s.p2-s.p1, p-s.p1) < 0:
        return abs(p-s.p1)
    if dot(s.p1-s.p2, p-s.p2) < 0:
        return abs(p-s.p2)
    return get_distance_lp(s, p)

def intersect(s1, s2):
    return True
    
def get_distance(s1, s2):
    if intersect(s1, s2):
        return 0
    return min([get_distance_sp(s1, s2.p1), get_distance_sp(s1, s2.p2),
                get_distance_sp(s2, s1.p1), get_distance_sp(s2, s1.p2)])

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 a.norm() < b.norm():
        return ONLINE_FRONT
    return ON_SEGMENT

from functools import singledispatch
@singledispatch
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)

@intersect.register(Segment)
def _(s1, s2):
    return intersect(s1.p1, s1.p2, s2.p1, s2.p2)


if __name__ == '__main__':
    from sys import stdin
    input = stdin.readline

    

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

Solution (Python):


q = input()

for loop in range(q):
    x0, y0, x1, y1, x2, y2, x3, y3 = map(int, raw_input().split())
    
    a1, b1, c1 = [y1 - y0, x0 - x1, x0 * (y1 - y0) - y0 * (x1 - x0)]
    a2, b2, c2 = [y3 - y2, x2 - x3, x2 * (y3 - y2) - y2 * (x3 - x2)]
    det = a1 * b2 - b1 * a2
    
    if det == 0:
        if x0 * a1 + y0 * b1 != x2 * a1 + y2 * b1: 
            print 0
        elif max(x0, x1) < min(x2, x3) or max(x2, x3) < min(x0, x1) \
            or max(y0, y1) < min(y2, y3) or max(y2, y3) < min(y0, y1): 
            print 0
        else: 
            print 1
        continue

    if (a1 * x2 + b1 * y2 - c1) * (a1 * x3 + b1 * y3 - c1) <= 0 and \
        (a2 * x0 + b2 * y0 - c2) * (a2 * x1 + b2 * y1 - c2) <= 0:
        print 1
    else:
        print 0

Solution (Python):
def cross(v1,v2):
	return v1.real*v2.imag-v1.imag*v2.real

def isOnSegment(p1,p2,p):
	return abs(p1-p)+abs(p2-p)-abs(p1-p2)<=1e-8

def isIntersection(p1,p2,p3,p4):
	if cross(p2-p1,p4-p3)==0:
		return any(isOnSegment(q1,q2,q3)for q1,q2,q3 in ((p1,p2,p3),(p1,p2,p4),(p3,p4,p1),(p3,p4,p2)))
	return cross(p2-p1,p3-p1)*cross(p2-p1,p4-p1)<=1e-8>=cross(p4-p3,p1-p3)*cross(p4-p3,p2-p3)

import sys
input = sys.stdin.buffer.readline
ans=[]
for _ in range(int(input())):
	m=map(int,input().split())
	ans.append(int(isIntersection(*[complex(x,y)for x,y in zip(*[iter(m)]*2)])))
print("\n".join(map(str,ans)))

Solution (Python):
from math import pi, cos, sin, atan2
EPS = 10**(-9)

def eq(value1, value2):
    return abs(value1-value2) <= EPS

class Point():
    def __init__(self, x, y):
        self.x = x
        self.y = y
        self.arg = atan2(y, x) 
    
    def __str__(self):
        return "{0:.8f} {1:.8f}".format(self.x, self.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, scal):
        return Point(self.x*scal, self.y*scal)
    
    def __truediv__(self, scal):
        return Point(self.x/scal, self.y/scal)
    
    def __eq__(self, other):
        return eq(self.x, other.x) and eq(self.y, other.y)

    
    def __abs__(self):
        return (self.x**2+self.y**2)**0.5
    

def Rotation(vec: Point, rad):
    return Point(vec.x*cos(rad)-vec.y*sin(rad), vec.x*sin(rad)+vec.y*cos(rad))


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


class Line():
    
    def __init__(self, a, b):
        self.a = a
        self.b = b
        self.arg = (a-b).arg % pi
    
    def __str__(self):
        return "[({0}, {1}) - ({2}, {3})]".format(self.a.x, self.a.y, self.b.x, self.b.y)

    
    def par(self, point):
        return Line(point, point+(self.a-self.b))

    
    def tan(self, point):
        return Line(point, point + Rotation(self.a-self.b, pi/2))


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



def cross(vec1: Point, vec2: Point):
    return vec1.x*vec2.y - vec1.y*vec2.x


def dot(vec1: Point, vec2: Point):
    return vec1.x*vec2.x + vec1.y*vec2.y


def ccw(a, b, c):
    if cross(b-a, c-a) > EPS: return +1 
    if cross(b-a, c-a) < -EPS: return -1 
    if dot(c-a, b-a) < -EPS: return +2 
    if abs(b-a) < abs(c-a): return -2 
    return 0 



def projection(l, p):
    t = dot(l.b-l.a, p-l.a) / abs(l.a-l.b)**2
    return l.a + (l.b-l.a)*t


def reflection(l, p):
    return p + (projection(l, p) - p)*2

def isPararell(l1, l2):
    return eq(cross(l1.a-l1.b, l2.a-l2.b), 0)

def isVertical(l1, l2):
    return eq(dot(l1.a-l1.b, l2.a-l2.b), 0)


def isIntersect_lp(l, p):
    return abs(ccw(l.a, l.b, p)) != 1

def isIntersect_ll(l1, l2):
    return not isPararell(l1, l2) or isIntersect_lp(l1, l2.a)

def isIntersect_sp(s, p):
    return ccw(s.a, s.b, p) == 0

def isIntersect_ss(s1, s2):
    return ccw(s1.a, s1.b, s2.a)*ccw(s1.a, s1.b, s2.b) <= 0 and ccw(s2.a, s2.b, s1.a)*ccw(s2.a, s2.b, s1.b) <= 0

def isIntersect_ls(l, s):
    return cross(l.b - l.a, s.a - l.a) * cross(l.b - l.a, s.b - l.a) < EPS

def isIntersect_cp(c, p):
    return abs(abs(c.p - p) - c.r) < EPS

def isIntersect_cl(c, l):
    return distance_lp(l, c.p) <= c.r + EPS

def isIntersect_cs(c, s):
    pass

def isIntersect_cc(c1, c2):
    pass


def distance_pp(p1, p2):
    return abs(p1-p2)

def distance_lp(l, p):
    return abs(projection(l,p)-p)

def distance_ll(l1, l2):
    return 0 if isIntersect_ll(l1, l2) else distance_lp(l1, l2.a)

def distance_sp(s, p):
    r = projection(s, p)
    if isIntersect_sp(s, r): return abs(r-p)
    return min(abs(s.a-p), abs(s.b-p))

def distance_ss(s1, s2):
    if isIntersect_ss(s1, s2): return 0
    return min([distance_sp(s1, s2.a), distance_sp(s1, s2.b), distance_sp(s2, s1.a), distance_sp(s2, s1.b)])

def distance_ls(l, s):
    if isIntersect_ls(l, s): return 0
    return min(distance_lp(l, s.a), distance_lp(l, s.b))


def crosspoint_ll(l1, l2):
    A = cross(l1.b - l1.a, l2.b - l2.a)
    B = cross(l1.b - l1.a, l1.b - l2.a)
    if eq(abs(A), 0) and eq(abs(B), 0): return l2.a
    return l2.a + (l2.b - l2.a) * B / A

def crosspoint_ss(s1, s2):
    return crosspoint_ll(s1, s2)

def crosspoint_lc(l, c):
    if eq(distance_lp(l, c.p), c.r): return [c.p]
    p = projection(l, c.p)
    e = (l.b - l.a) / abs(l.b-l.a)
    dis = (c.r**2-abs(p-c.p)**2)**0.5
    return [p + e*dis, p - e*dis]

def crosspoint_sc(s, c):
    pass

def crosspoint_cc(c1, c2):
    d = abs(c1.p-c2.p)
    if not abs(c1.r-c2.r) <= d <= c1.r+c2.r:
        return []
    mid_p = (c2.p * (c1.r**2-c2.r**2+d**2) + c1.p * (c2.r**2-c1.r**2+d**2)) / (2*d**2)
    tanvec = Rotation(c1.p-c2.p, pi/2)
    return crosspoint_lc(Line(mid_p, mid_p+tanvec), c1)



def tangent_cp(c, p):
    return crosspoint_cc(c, Circle(p, (abs(p-c.p)**2 - c.r**2)**0.5))





import sys
input = sys.stdin.readline

def verify_1A():
    p1x, p1y, p2x, p2y = map(int, input().split())
    l = Line(Point(p1x, p1y), Point(p2x, p2y))
    Q = int(input())
    Query = [list(map(int, input().split())) for _ in range(Q)]
    for px, py in Query:
        p = Point(px, py)
        print(projection(l, p))

def verify_1B():
    p1x, p1y, p2x, p2y = map(int, input().split())
    l = Line(Point(p1x, p1y), Point(p2x, p2y))
    Q = int(input())
    Query = [list(map(int, input().split())) for _ in range(Q)]
    for px, py in Query:
        p = Point(px, py)
        print(reflection(l, p))

def verify_1C():
    p1x, p1y, p2x, p2y = map(int, input().split())
    p1 = Point(p1x, p1y); p2 = Point(p2x, p2y)
    Q = int(input())
    Query = [list(map(int, input().split())) for _ in range(Q)]
    for px, py in Query:
        p = Point(px, py)
        result = ccw(p1, p2, p)
        if result == 1:
            print("COUNTER_CLOCKWISE")
        elif result == -1:
            print("CLOCKWISE")
        elif result == 2:
            print("ONLINE_BACK")
        elif result == -2:
            print("ONLINE_FRONT")
        else:
            print("ON_SEGMENT")

def verify_2A():
    Q = int(input())
    Query = [list(map(int, input().split())) for _ in range(Q)]
    for p0x, p0y, p1x, p1y, p2x, p2y, p3x, p3y in Query:
        l1 = Line(Point(p0x, p0y), Point(p1x, p1y))
        l2 = Line(Point(p2x, p2y), Point(p3x, p3y))
        if isPararell(l1, l2):
            print(2)
        elif isVertical(l1, l2):
            print(1)
        else:
            print(0)

def verify_2B():
    Q = int(input())
    Query = [list(map(int, input().split())) for _ in range(Q)]
    for p0x, p0y, p1x, p1y, p2x, p2y, p3x, p3y in Query:
        s1 = Segment(Point(p0x, p0y), Point(p1x, p1y))
        s2 = Segment(Point(p2x, p2y), Point(p3x, p3y))
        if isIntersect_ss(s1, s2):
            print(1)
        else:
            print(0)
verify_2B()

Solution (Python):
def on_segment(u0,v0,u1,v1,u2,v2):
     return u1<=max(u0,u2) and u1>=min(u0,u2) and v1<=max(v0,v2) and v1>=min(v0,v2)

def signed_area(x0,y0,x1,y1):
    return (x0*y1-x1*y0)

q=int(input())

for _ in [0]*q:
    x0,y0,x1,y1,x2,y2,x3,y3=map(int,input().split())
    ta=signed_area(x1-x0,y1-y0,x2-x0,y2-y0)
    tb=signed_area(x1-x0,y1-y0,x3-x0,y3-y0)
    tc=signed_area(x3-x2,y3-y2,x0-x2,y0-y2)
    td=signed_area(x3-x2,y3-y2,x1-x2,y1-y2)

    """
    print(ta/2)
    print(tb/2)
    print(tc/2)
    print(td/2)
    
    print(on_segment(x0,y0,x2,y2,x1,y1))
    print(on_segment(x0,y0,x3,y3,x1,y1))
    print(on_segment(x2,y2,x0,y0,x3,y3))
    print(on_segment(x2,y2,x1,y1,x3,y3))
    """

    if ta*tb<0 and tc*td<0:
        print("1")
    elif ta==0 and on_segment(x0,y0,x2,y2,x1,y1):
        print("1")
    elif tb==0 and on_segment(x0,y0,x3,y3,x1,y1):
        print("1")
    elif tc==0 and on_segment(x2,y2,x0,y0,x3,y3):
        print("1")
    elif td==0 and on_segment(x2,y2,x1,y1,x3,y3):
        print("1")
    else:
        print("0")