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 sys import stdin

EPS = 1e-10

class Vector:
    def __init__(self, x=None, y=None):
        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, k):
        return Vector(self.x * k, self.y * k)

    def __gt__(self, other):
        return self.x > other.x and self.y > other.yb

    def __lt__(self, other):
        return self.x < other.x and self.y < other.yb

    def __eq__(self, other):
        return self.x == other.x and self.y == other.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 norm(self):
        return self.x * self.x + self.y * self.y

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

class Point(Vector):
    def __init__(self, *args, **kargs):
        return super().__init__(*args, **kargs)

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

def ccw(p0, p1, p2):
    a = p1 - p0
    b = p2 - p0
    if a.cross(b) > EPS:
        return 1
    elif a.cross(b) < -EPS:
        return -1
    elif a.dot(b) < -EPS:
        return 2
    elif a.norm() < b.norm():
        return -2
    else:
        return 0

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

def read_and_print_results(n):
    for _ in range(n):
        line = stdin.readline().strip().split()
        p0 = Vector(int(line[0]), int(line[1]))
        p1 = Vector(int(line[2]), int(line[3]))
        p2 = Vector(int(line[4]), int(line[5]))
        p3 = Vector(int(line[6]), int(line[7]))
        if intersect(p0, p1, p2, p3):
            print(1)
        else:
            print(0)

n = int(input())
read_and_print_results(n)

Solution (Python):
from sys import stdin
readline = stdin.readline


def main():
    q = int(readline())
    for i in range(q):
        xy = map(int, readline().split())
        p0, p1, p2, p3 = [x + y * 1j for x, y in zip(*[xy] * 2)]
        print(1 if is_intersected_ls(p0, p1, p2, p3) else 0)


def is_intersected_ls(a1, a2, b1, b2):
    eps = 0
    if max(a1.real, a2.real) < min(b1.real, b2.real)\
      or max(b1.real, b2.real) < min(a1.real, a2.real)\
      or max(a1.imag, a2.imag) < min(b1.imag, b2.imag)\
      or max(b1.imag, b2.imag) < min(a1.imag, a2.imag):
        return False

    
    
    
    
    return (cross(a2-a1, b1-a1) * cross(a2-a1, b2-a1) <= eps)\
        and (cross(b2-b1, a1-b1) * cross(b2-b1, a2-b1) <= eps)


def cross(a, b):
    return a.real * b.imag - a.imag * b.real
main()

Solution (Python):
from itertools import starmap


def cross(a, b):
    return a.real * b.imag - a.imag * b.real


q = int(input())
while q:
    q -= 1
    p0, p1, p2, p3 = starmap(complex, zip(*[map(int, input().split())] * 2))
    max_x1, min_x1 = (p0.real, p1.real) if p0.real > p1.real else (p1.real, p0.real)
    max_y1, min_y1 = (p0.imag, p1.imag) if p0.imag > p1.imag else (p1.imag, p0.imag)
    max_x2, min_x2 = (p2.real, p3.real) if p2.real > p3.real else (p3.real, p2.real)
    max_y2, min_y2 = (p2.imag, p3.imag) if p2.imag > p3.imag else (p3.imag, p2.imag)
    if any((max_x1 < min_x2, max_x2 < min_x1, max_y1 < min_y2, max_y2 < min_y1)):
        print(0)
        continue

    print(int(cross(p1 - p0, p2 - p0) * cross(p1 - p0, p3 - p0) < 1e-6 and
              cross(p3 - p2, p0 - p2) * cross(p3 - p2, p1 - p2) < 1e-6))

Solution (Python):
for t in xrange(input()):
    x0, y0, x1, y1, x2, y2, x3, y3 = map(int, raw_input().split())
    dx0 = x1 - x0
    dy0 = y1 - y0
    dx1 = x3 - x2
    dy1 = y3 - y2

    s = (y0-y2)*dx1 - (x0-x2)*dy1
    sm = dx0*dy1 - dy0*dx1
    if s < 0:
        s = -s
        sm = -sm
    t = (y2-y0)*dx0 - (x2-x0)*dy0
    tm = dx1*dy0 - dy1*dx0
    if t < 0:
        t = -t
        tm = -tm
    if 0 <= s <= max(sm, 0) and 0 <= t <= max(tm, 0):
        ov = dx0*dy1 - dy0*dx1
        if ov == 0:
            r0 = dx0**2 + dy0**2
            r1 = (x2-x0)*dx0 + (y2-y0)*dy0
            r2 = (x3-x0)*dx0 + (y3-y0)*dy0
            if r1 > r2: r1, r2 = r2, r1
            if r2 < 0 or r0 < r1:
                print 0
            else:
                print 1
        else:
            print 1
    else:
        print 0

Solution (Python):
q = int(raw_input())
for _ in xrange(q):
  x0,y0,x1,y1,x2,y2,x3,y3 = map(float, raw_input().split())
  ta = (x2 - x3) * (y0 - y2) + (y2 - y3) * (x2 - x0)
  tb = (x2 - x3) * (y1 - y2) + (y2 - y3) * (x2 - x1)
  tc = (x0 - x1) * (y2 - y0) + (y0 - y1) * (x0 - x2)
  td = (x0 - x1) * (y3 - y0) + (y0 - y1) * (x0 - x3)

  if tc * td <= 0 and ta * tb <= 0:
    if tc * td == 0 and ta * tb == 0:
      outer1 = (x2 - x0) * (x2 - x1) + (y2 - y0) * (y2 - y1)
      outer2 = (x3 - x0) * (x3 - x1) + (y3 - y0) * (y3 - y1)
      outer3 = (x0 - x2) * (x0 - x3) + (y0 - y2) * (y0 - y3)
      outer4 = (x1 - x2) * (x1 - x3) + (y1 - y2) * (y1 - y3)
      if outer1 <= 0 or outer2 <= 0 or outer3 <= 0 or outer4 <= 0:
        print 1
      else:
        print 0
    else:
      print 1
  else:
    print 0

Solution (Python):



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

output:
1
1
0
"""

import sys

EPS = 1e-9


def cross(a, b):
    return a.real * b.imag - a.imag * b.real


def dot(a, b):
    return a.real * b.real + a.imag * b.imag


def check_ccw(p0, p1, p2):
    
    a, b = p1 - p0, p2 - p0
    if cross(a, b) > EPS:
        
        flag = 1
    elif cross(a, b) < -1 * EPS:
        
        flag = -1
    elif dot(a, b) < -1 * EPS:
        
        flag = 2
    elif abs(a) < abs(b):
        
        flag = -2
    else:
        
        flag = 0
    return flag


def check_intersection(_lines):
    for line in _lines:
        line = tuple(map(int, line))
        p0, p1, p2, p3 = (x + y * 1j for x, y in zip(line[::2], line[1::2]))
        flag = (check_ccw(p0, p1, p2) * check_ccw(p0, p1, p3) <= 0) and \
               (check_ccw(p2, p3, p0) * check_ccw(p2, p3, p1) <= 0)

        if flag:
            print('1')
        else:
            print('0')

    return None


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    l_num = int(_input[0])
    lines = map(lambda x: x.split(), _input[1:])

    check_intersection(lines)

Solution (Python):



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

output:
1
1
0
"""

import sys

EPS = 1e-9


def cross(a, b):
    return a.real * b.imag - a.imag * b.real


def dot(a, b):
    return a.real * b.real + a.imag * b.imag


def check_ccw(p0, p1, p2):
    a, b = p1 - p0, p2 - p0
    if cross(a, b) > EPS:
        flag = 1
    elif cross(a, b) < -1 * EPS:
        flag = -1
    elif dot(a, b) < -1 * EPS:
        flag = 2
    elif abs(a) < abs(b):
        flag = -2
    else:
        flag = 0
    return flag


def check_intersection(p0, p1, p2, p3):
    intersected = (check_ccw(p0, p1, p2) * check_ccw(p0, p1, p3) <= 0) and \
                  (check_ccw(p2, p3, p0) * check_ccw(p2, p3, p1) <= 0)

    return intersected


def solve(_lines):
    for line in _lines:
        line = tuple(map(int, line))
        p0, p1, p2, p3 = (x + y * 1j for x, y in zip(line[::2], line[1::2]))
        intersected = check_intersection(p0, p1, p2, p3)

        if intersected:
            print('1')
        else:
            print('0')
    return None


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    l_num = int(_input[0])
    lines = map(lambda x: x.split(), _input[1:])

    solve(lines)

Solution (Python):
class Point:
    def __init__(self, x , y):
        self.x = x
        self.y = y
    def __sub__(self, p):
        x_sub = self.x - p.x
        y_sub = self.y - p.y
        return Point(x_sub, y_sub)

class Vector:
    def __init__(self, p):
        self.x = p.x
        self.y = p.y
    def norm(self):
        return (self.x ** 2 + self.y ** 2) ** 0.5

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

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

def ccw(p0, p1, p2):
    a = Vector(p1 - p0)
    b = Vector(p2 - p0)
    cross_ab = cross(a, b)
    if cross_ab > 0:
        return 1
    elif cross_ab < 0:
        return -1
    elif dot(a, b) < 0:
        return 1
    elif a.norm() < b.norm():
        return -1
    else:
        return 0

def intersect(p1, p2, p3, p4):
    if (ccw(p1, p2, p3) * ccw(p1, p2, p4) <= 0) and \
       (ccw(p3, p4, p1) * ccw(p3, p4, p2) <= 0):
        print('1')
    else:
        print('0')

import sys

file_input = sys.stdin

sq = file_input.readline()

for line in file_input:
    x_p0, y_p0, x_p1, y_p1, x_p2, y_p2, x_p3, y_p3 = map(int, line.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)
    intersect(p0, p1, p2, p3)

Solution (Python):
import sys
from itertools import starmap
readline = sys.stdin.readline
EPS = 1e-9
ONLINE_FRONT = -2
CLOCKWISE = -1
ON_SEGMENT = 0
COUNTER_CLOCKWISE = 1
ONLINE_BACK = 2
class Segment(object):
    __slots__ = ('fi', 'se')
    def __init__(self, fi, se):
        self.fi = fi
        self.se = se
def cross(a, b):
    return a.real * b.imag - a.imag * b.real
def dot(a, b):
    return a.real * b.real + a.imag * b.imag
def norm(base):
    return abs(base) ** 2
def project(s, p2):
    base = s.fi - s.se
    r = dot(p2 - s.fi, base) / norm(base)
    return s.fi + base * r
def reflect(s, p):
    return p + (project(s, p) - p) * 2.0
def ccw(p1, p2, p3):
    a = p2 - p1
    b = p3 - p1
    if cross(a, b) > EPS: return 1
    if cross(a, b) < -EPS: return -1
    if dot(a, b) < -EPS: return 2
    if norm(a) < norm(b): return -2
    return 0
def intersect4(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 intersect2(s1, s2):
    return intersect4(s1.fi, s1.se, s2.fi, s2.se)
def getDistance(a, b):  return abs(a - b)
def getDistanceLP(l, p):
    return abs(cross(l.se - l.fi, p - l.fi) / abs(l.se - l.fi))
def getDistanceSP(s, p):
    if dot(s.se - s.fi, p - s.fi) < 0.0: return abs(p - s.fi)
    if dot(s.fi - s.se, p - s.se) < 0.0: return abs(p - s.se)
    return getDistanceLP(s, p)
def getDistances(s1, s2):
    if intersect2(s1, s2): return 0.0
    return min(getDistanceSP(s1, s2.fi), getDistanceSP(s1, s2.se),
               getDistanceSP(s2, s1.fi), getDistanceSP(s2, s1.se))
n = int(readline())
for _ in [0] * n:
    p0, p1, p2, p3 = starmap(complex, zip(*[map(int, input().split())] * 2))
    print(1 if intersect4(p0, p1, p2, p3) else 0)

Solution (Python):
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 isOn(a,b):
    if cross(a,b) == 0:
        if dot(a,b) < 0 or dot(a,a) < dot(b,b) : return False
        else : return True
    else : 
        return False

q = int(input())
for i in range(q):
    x0,y0,x1,y1,x2,y2,x3,y3 = [int(i) for i in input().split()]
    a = [x1-x0,y1-y0]
    b = [x2-x0,y2-y0]
    c = [x3-x0,y3-y0]
    d = [x3-x2,y3-y2]
    e = [x0-x2,y0-y2]
    f = [x1-x2,y1-y2]
    if isOn(a,b) or isOn(a,c):
        print(1)
    elif cross(a,b) == 0 and cross(a,c) == 0:
        if ( not isOn(c,a) and isOn(b,a)) or (isOn(c,a) and not isOn(b,a)) :
            print(1)
        else:
            print(0)
    elif cross(a,b) * cross(a,c) > 0 :
        print(0)
    elif cross(d,e) * cross(d,f) > 0 :
        print(0)
    else :
        print(1)

Solution (Python):
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 isOn(l,m):
    a = dif(l.e,l.s);b = dif(m.s,l.s);c = dif(m.e,l.s)
    d = dif(m.e,m.s);e = dif(l.s,m.s);f = dif(l.e,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
    else:return False
        
    
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)
    if isOn(l,m):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(a,b) ; l2 = Line(c,d)
    if InterSection(l1,l2):print(1)
    else:print(0)

Solution (Python):
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(a,b) ; l2 = Line(c,d)
    if InterSection(l1,l2):print(1)
    else:print(0)

Solution (Python):
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,a) ; l2 = Line(d,c)
    if InterSection(l1,l2):print(1)
    else:print(0)

Solution (Python):
def cross(a,b):return a[0]*b[1] - a[1]*b[0]

q = range(int(input()))
for i in q:
    a,b,c,d,e,f,g,h = [int(x) for x in input().split()]
    A = [c-a,d-b]; B = [e-a,f-b]; C = [g-a,h-b];
    D = [g-e,h-f]; E = [a-e,b-f]; F = [c-e,d-f];
    if max(a,c) < min(e,g) or max(e,g) < min(a,c) or max(b,d) < min(f,h) or max(f,h) < min(b,d):
        print("0")
    elif cross(A,B) * cross(A,C) <= 0 and cross(D,E) * cross(D,F) <= 0:
        print("1")
    else:
        print("0")

Solution (Python):


import sys, math, os


PYDEV = os.environ.get('PYDEV')
if PYDEV=="True":
    sys.stdin = open("sample-input.txt", "rt")


def on_segment(p, q, r):
    
    
    return q[0] <= max(p[0], r[0]) and q[0] >= min(p[0], r[0]) and \
           q[1] <= max(p[1], r[1]) and q[1] >= min(p[1], r[1])

def orientation(p, q, r):
    
    
    
    
    
    val = (q[1] - p[1]) * (r[0] - q[0]) - (q[0] - p[0]) * (r[1] - q[1])
    if val == 0:
        return 0
    return 1 if val > 0 else 2

def do_intersect(p1, q1, p2, q2):
    
    
    o1 = orientation(p1, q1, p2)
    o2 = orientation(p1, q1, q2)
    o3 = orientation(p2, q2, p1)
    o4 = orientation(p2, q2, q1)
    
    
    if o1 != o2 and o3 != o4:
        return True
    
    
    
    
    if o1 == 0 and on_segment(p1, p2, q1):
        return True
    
    if o2 == 0 and on_segment(p1, q2, q1):
        return True
    
    if o3 == 0 and on_segment(p2, p1, q2):
        return True
    
    if o4 == 0 and on_segment(p2, q1, q2):
        return True
    
    return False


n = int(input())
for k in range(n):
    x1, y1, x2, y2, x3, y3, x4, y4 = [int(_) for _ in input().split()]
    print(1 if do_intersect([x1, y1], [x2, y2], [x3, y3], [x4, y4]) else 0)

Solution (Python):

"""
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 
    elif Vector.cross(a, b) < -epsilon:
        return -1 
    elif Vector.dot(a, b) < -epsilon:
        return 2 
    elif a.norm() < b.norm():
        return -2 
    else:
        return 0 


def intersect(p0, p1, p2, p3):
    ans1 = ccw(p0, p1, p2) * ccw(p0, p1, p3)
    ans2 = ccw(p2, p3, p0) * ccw(p2, p3, p1)
    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)
        print(int(result))


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

Solution (Python):

"""
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 
    elif Vector.cross(a, b) < -epsilon:
        return -1 
    elif Vector.dot(a, b) < -epsilon:
        return 2 
    elif a.norm() < b.norm():
        return -2 
    else:
        return 0 


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)
        

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


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

Solution (Python):

"""


"""
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):
        
        a = Vector(p1 - p0)
        b = Vector(self - p0)
        if Vector.cross(a, b) > Point.epsilon:
            return 1 
        elif Vector.cross(a, b) < -Point.epsilon:
            return -1 
        elif Vector.dot(a, b) < -Point.epsilon:
            return 2 
        elif a.norm() < b.norm():
            return -2 
        else:
            return 0 

    def project(self, 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):
        
        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:])

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

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