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:
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):
    return (cross(a2-a1, b1-a1) * cross(a2-a1, b2-a1) < 1e-10) and (cross(b2-b1, a1-b1) * cross(b2-b1, a2-b1) < 1e-10)


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

Submission status: Wrong Answer

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

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

Solution code:
# coding: utf-8

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

def is_Crossed(OA, OC, OB, OD):
    """
    AOJ: CGL_2B 
    ref. http://www.fumiononaka.com/Business/html5/FN1312004.html
    """
    AC = Point(OC.x - OA.x, OC.y - OA.y)
    BD = Point(OD.x - OB.x, OD.y - OB.y)
    AB = Point(OB.x - OA.x, OB.y - OA.y)
    BC = Point(OC.x - OB.x, OC.y - OB.y)
    AD = Point(OD.x - OA.x, OD.y - OA.y)
    BA = Point(-AB.x, -AB.y)
	
    if crossProduct2D(AC, BD) == 0: return 0
    if crossProduct2D(BD, BA) * crossProduct2D(BD, BC) > 0: return 0
    else:
	    if crossProduct2D(AC, AB) * crossProduct2D(AC, AD) > 0: return 0
	    else: return 1
	        
def crossProduct2D(Point0, Point1):
    return Point0.x * Point1.y - Point0.y * Point1.x

if __name__ == "__main__":
    n = int(raw_input())
    for i in range(n):
        xp0, yp0, xp1, yp1, xp2, yp2, xp3, yp3 = map(int,raw_input().split())
        P0 = Point(xp0, yp0)
        P1 = Point(xp1, yp1)
        P2 = Point(xp2, yp2)
        P3 = Point(xp3, yp3)
        print is_Crossed(P0, P1, P2, P3)

Submission status: Wrong Answer

Solution code:
# coding: utf-8

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

def is_Crossed(OA, OC, OB, OD):
    """
    AOJ: CGL_2B 
    segment AC and segment BD
    ref. http://www.fumiononaka.com/Business/html5/FN1312004.html
    """
    AC = Point(OC.x - OA.x, OC.y - OA.y)
    BD = Point(OD.x - OB.x, OD.y - OB.y)
    AB = Point(OB.x - OA.x, OB.y - OA.y)
    BC = Point(OC.x - OB.x, OC.y - OB.y)
    AD = Point(OD.x - OA.x, OD.y - OA.y)
    BA = Point(-AB.x, -AB.y)
	
    if crossProduct2D(AC, BD) == 0:
        if (OA.x, OA.y) == (OD.x, OD.y) or (OB.x, OB.y) == (OC.x, OC.y):
            return 1
        else:
            return 0
    if crossProduct2D(BD, BA) * crossProduct2D(BD, BC) > 0: 
        return 0
    else:
	    if crossProduct2D(AC, AB) * crossProduct2D(AC, AD) > 0: 
	        return 0
	    else: 
	        return 1
	        
def crossProduct2D(Point0, Point1):
    return Point0.x * Point1.y - Point0.y * Point1.x

if __name__ == "__main__":
    n = int(raw_input())
    for i in range(n):
        xp0, yp0, xp1, yp1, xp2, yp2, xp3, yp3 = map(int,raw_input().split())
        P0 = Point(xp0, yp0)
        P1 = Point(xp1, yp1)
        P2 = Point(xp2, yp2)
        P3 = Point(xp3, yp3)
        print is_Crossed(P0, P1, P2, P3)

Submission status: Wrong Answer

Solution code:
# coding: utf-8

class Point:
    def __init__(self, x, y):
        self.x = x
        self.y = y
        
import itertools
def is_the_same_points_included(OA, OC, OB, OD):
    args = [OA, OC, OB, OD]
    for first,second in itertools.combinations(args,2):
        if (first.x, first.y) == (second.x, second.y):
            return True
    else:
        return False

def is_Crossed(OA, OC, OB, OD):
    """
    AOJ: CGL_2B 
    segment AC and segment BD
    ref. http://www.fumiononaka.com/Business/html5/FN1312004.html
    """
    AC = Point(OC.x - OA.x, OC.y - OA.y)
    BD = Point(OD.x - OB.x, OD.y - OB.y)
    AB = Point(OB.x - OA.x, OB.y - OA.y)
    BC = Point(OC.x - OB.x, OC.y - OB.y)
    AD = Point(OD.x - OA.x, OD.y - OA.y)
    BA = Point(-AB.x, -AB.y)
	
    if crossProduct2D(AC, BD) == 0:
        if is_the_same_points_included(OA, OC, OB, OD):
            return 1
        else:
            return 0
    if crossProduct2D(BD, BA) * crossProduct2D(BD, BC) > 0: 
        return 0
    else:
	    if crossProduct2D(AC, AB) * crossProduct2D(AC, AD) > 0: 
	        return 0
	    else: 
	        return 1
	        
def crossProduct2D(Point0, Point1):
    return Point0.x * Point1.y - Point0.y * Point1.x

if __name__ == "__main__":
    n = int(raw_input())
    for i in range(n):
        xp0, yp0, xp1, yp1, xp2, yp2, xp3, yp3 = map(int,raw_input().split())
        P0 = Point(xp0, yp0)
        P1 = Point(xp1, yp1)
        P2 = Point(xp2, yp2)
        P3 = Point(xp3, yp3)
        print is_Crossed(P0, P1, P2, P3)

Submission status: Wrong Answer

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

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 (p2.real, p3.real)
    max_y2, min_y2 = (p2.imag, p3.imag) if p2.imag > p3.imag else (p2.imag, p3.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: Wrong Answer

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 <= sm and 0 <= t <= tm:
        print 1
    else:
        print 0

Submission status: Wrong Answer

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
    ov = dx0*dy1 - dy0*dx1
    if ov == 0:
        print 0
    elif 0 <= s <= sm and 0 <= t <= tm:
        print 1
    else:
        print 0

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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:
    print 1
  else:
    print 0

Submission status: Wrong Answer

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)
      if outer1 <= 0 or outer2 <= 0:
        print 1
      else:
        print 0
    else:
      print 1
  else:
    print 0

Submission status: Wrong Answer

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 cross(v1, v2):
    return v1.x * v2.y - v1.y * v2.x

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

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) * cross(a,c) > 0 :
        print(0)
    elif cross(d,e) * cross(d,f) > 0 :
        print(0)
    else :
        print(1)

Submission status: Wrong Answer

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:
        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,isOn(a,b),isOn(a,c))

Submission status: Wrong Answer

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

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) or isOn(c,a) or isOn(b,a):
        print(1)
    elif cross(a,b) == 0 and cross(a,c) == 0:
        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: Wrong Answer

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(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
    
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 cross(a,d) == 0 and (isOn(b,a) or isOn(c,a) or isOn(e,d) or isOn(f,d)):
        print(isOn(b,a),isOn(c,a),isOn(e,d),isOn(f,d))
        print("here1")
        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: Wrong Answer

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(l.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
    
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 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: Wrong Answer

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)
    print(a,b,c,d,e,f)
    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)
    print(a,b,c,d,e,f)
    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: Wrong Answer

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-a];
    D = [g-e,h-f]; E = [a-e,b-f]; F = [c-e,d-f];
    T = max(a,c) < min(e,g)
    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: Wrong Answer

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-a];
    D = [g-e,h-f]; E = [a-e,b-f]; F = [c-e,d-f];
    T = max(a,c) < min(e,g)
    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) <= 1e-12 and cross(D,E) * cross(D,F) <= 1e-12:
        print("1")
    else:
        print("0")

Submission status: Wrong Answer

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 1 # 'ONLINE_BACK'
    elif a.norm() < b.norm():
        return 1 # '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:])

Submission status: Wrong Answer

Solution code:
q = int(input())

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
    return 0

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

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

Submission status: Wrong Answer

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

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

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

def sub(a, b):
    return [a[0] - b[0],a[1] - b[1]]

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

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

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

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

Submission status: Wrong Answer

Solution code:
import math

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
        self.intersept = 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)
            self.intersept = self.p1.y - self.slope*self.p1.x

    def is_in_range(self, x, y):
        return ((x - self.p1.x)*(x - self.p2.x) <= 0 and (y - self.p1.y)*(y - self.p2.y) <= 0)

    def is_intersect(self, seg):
        if self.slope == seg.slope: return False
        slope_diff = seg.slope - self.slope
        if self.slope == float('inf'):
            x = self.p1.x
            y = seg.slope * x + seg.intersept
        elif seg.slope == float('inf'):
            x = seg.p1.x
            y = self.slope * x + self.intersept
        else:
            x = -(seg.intersept - self.intersept)/slope_diff
            y = self.slope * x + self.intersept
        if seg.is_in_range(x, y) and self.is_in_range(x, y): return True
        return False

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:
import math

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)

    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)

    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):
        if self.slope == seg.slope: return False
        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)