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: Wrong Answer

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)
        return a*b <= 0 and c*d <= 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: Wrong Answer

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*f <= 0 and g*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: Wrong Answer

Solution code:
# coding=utf-8


def cross_product(vect1, vect2):
    return vect1[0]*vect2[1] - vect1[1]*vect2[0]


def vector_minus(vect1, vect2):
    return [el1 - el2 for el1, el2 in zip(vect1, vect2)]


def is_cross(l_from1, l_to1, l_from2, l_to2):
    line1 = vector_minus(l_to1, l_from1)
    line2 = vector_minus(l_to2, l_from2)

    from1_to2_1 = vector_minus(l_from2, l_from1)
    from1_to2_2 = vector_minus(l_to2, l_from1)

    from2_to1_1 = vector_minus(l_from1, l_from2)
    from2_to1_2 = vector_minus(l_to1, l_from2)

    if cross_product(line1, from1_to2_1)*cross_product(line1, from1_to2_2) > 0:
        return 0
    if cross_product(line2, from2_to1_1)*cross_product(line2, from2_to1_2) > 0:
        return 0
    return 1


if __name__ == '__main__':
    Q = int(input())

    for i in range(Q):
        all_list = list(map(int, input().split()))
        p0_list = all_list[:2]
        p1_list = all_list[2:4]
        p2_list = all_list[4:6]
        p3_list = all_list[6:]

        if is_cross(p0_list, p1_list, p2_list, p3_list):
            print("1")
        else:
            print("0")

Submission status: Wrong Answer

Solution code:
# coding=utf-8


def cross_product(vect1, vect2):
    return vect1[0]*vect2[1] - vect1[1]*vect2[0]


def vector_minus(vect1, vect2):
    return [el1 - el2 for el1, el2 in zip(vect1, vect2)]


def is_cross(l_from1, l_to1, l_from2, l_to2):
    line1 = vector_minus(l_to1, l_from1)
    line2 = vector_minus(l_to2, l_from2)

    from1_to2_1 = vector_minus(l_from2, l_from1)
    from1_to2_2 = vector_minus(l_to2, l_from1)

    from2_to1_1 = vector_minus(l_from1, l_from2)
    from2_to1_2 = vector_minus(l_to1, l_from2)

    if cross_product(line1, from1_to2_1)*cross_product(line1, from1_to2_2) >= 0:
        return 0
    if cross_product(line2, from2_to1_1)*cross_product(line2, from2_to1_2) >= 0:
        return 0
    return 1


if __name__ == '__main__':
    Q = int(input())

    for i in range(Q):
        all_list = list(map(int, input().split()))
        p0_list = all_list[:2]
        p1_list = all_list[2:4]
        p2_list = all_list[4:6]
        p3_list = all_list[6:]

        if is_cross(p0_list, p1_list, p2_list, p3_list):
            print("1")
        else:
            print("0")

Submission status: Accepted

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

    # usually cross operation return Vector but it returns scalor
    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)

Submission status: Accepted

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

    #print(cross(a2-a1, b1-a1))
    #print(cross(a2-a1, b2-a1))
    #print(cross(b2-b1, a1-b1))
    #print(cross(b2-b1, a2-b1))
    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()

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

"""
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):
    # flag = float('inf')
    a, b = p1 - p0, p2 - p0
    if cross(a, b) > EPS:
        # print('COUNTER_CLOCKWISE')
        flag = 1
    elif cross(a, b) < -1 * EPS:
        # print('CLOCKWISE')
        flag = -1
    elif dot(a, b) < -1 * EPS:
        # print('ONLINE_BACK')
        flag = 2
    elif abs(a) < abs(b):
        # print('ONLINE_FRONT')
        flag = -2
    else:
        # print('ON_SEGMENT')
        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)

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
class Line:
    def __init__(self,p1,p2):
        if p1[1] < p2[1]:self.s=p2;self.e=p1
        elif p1[1] > p2[1]:self.s=p1;self.e=p2
        else:
            if p1[0] < p2[0]:self.s=p1;self.e=p2
            else:self.s=p2;self.e=p1
def dot(a,b):return a[0]*b[0] + a[1]*b[1]
def cross(a,b):return a[0]*b[1] - a[1]*b[0]
def dif(a,b):return [x-y for x,y in zip(a,b)]
def 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)

Submission status: Accepted

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

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

Submission status: Accepted

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

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# Aizu Problem CGL_2_B: Intersection
#
import sys, math, os

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


def on_segment(p, q, r):
    # Given three colinear points p, q, r, the function checks if
    # point q lies on line segment 'pr'
    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):
    # To find orientation of ordered triplet (p, q, r).
    # The function returns following values
    #   0 --> p, q and r are colinear
    #   1 --> Clockwise
    #   2 --> Counterclockwise
    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):
    # The main function that returns true if line segment 'p1q1'
    # and 'p2q2' intersect.
    o1 = orientation(p1, q1, p2)
    o2 = orientation(p1, q1, q2)
    o3 = orientation(p2, q2, p1)
    o4 = orientation(p2, q2, q1)
    #
    # General case:
    if o1 != o2 and o3 != o4:
        return True
    #
    # Special Cases:
    # 
    # p1, q1 and p2 are colinear and p2 lies on segment p1q1
    if o1 == 0 and on_segment(p1, p2, q1):
        return True
    # p1, q1 and p2 are colinear and q2 lies on segment p1q1
    if o2 == 0 and on_segment(p1, q2, q1):
        return True
    # p2, q2 and p1 are colinear and p1 lies on segment p2q2
    if o3 == 0 and on_segment(p2, p1, q2):
        return True
    #  p2, q2 and q1 are colinear and q1 lies on segment p2q2
    if o4 == 0 and on_segment(p2, q1, q2):
        return True
    # Doesn't fall in any of the above cases:
    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)

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