Given the coordinates of the endpoints(p1-q1 and p2-q2) of the two line-segments. Check if they intersect or not.
Example 1:
Input:
p1=(1,1)
q1=(10,1)
p2=(1,2)
q2=(10,2)
Output:
0
Explanation:
The two line segments formed 
by p1-q1 and p2-q2 do not intersect.
Example 2:
Input:
p1=(10,0)
q1=(0,10)
p2=(0,0)
q2=(10,10)
Output:
1
Explanation:
The two line segments formed 
by p1-q1 and p2-q2 intersect.
Your Task:
You don't need to read input or print anything. Your task is to complete the function doIntersect() which takes the four points as input parameters and returns 1 if the line segments intersect. Otherwise, it returns 0.
Expected Time Complexity:O(1)
Expected Auxillary Space:O(1)
 
Constraints:
-10^{6}<=X,Y(for all points)<=10^{6}

Source: geeksforgeeks | Difficulty: EASY
Tags: Geometry

Mathematics

Starter code: #User function Template for python3



class Solution:

    def doIntersect(self, p1, q1, p2, q2):

        #code here

   

Solutions:
class Solution:

	def doIntersect(self, p1, q1, p2, q2):

		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
			if val > 0:
				return 1
			return 2

		def onSegment(p, q, r):
			if 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])):
				return True
			return False
		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 1
		if o1 == 0 and onSegment(p1, p2, q1):
			return 1
		if o2 == 0 and onSegment(p1, q2, q1):
			return 1
		if o3 == 0 and onSegment(p2, p1, q2):
			return 1
		if o4 == 0 and onSegment(p2, q1, q2):
			return 1
		return 0


class Point:

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

class Solution:

	def doIntersect(self, p1, q1, p2, q2):
		pt1 = Point(p1[0], p1[1])
		qt1 = Point(q1[0], q1[1])
		pt2 = Point(p2[0], p2[1])
		qt2 = Point(q2[0], q2[1])
		o1 = self.orientation(pt1, qt1, pt2)
		o2 = self.orientation(pt1, qt1, qt2)
		o3 = self.orientation(pt2, qt2, pt1)
		o4 = self.orientation(pt2, qt2, qt1)
		if o1 != o2 and o3 != o4:
			return 1
		if o1 == 0 and self.onSegment(pt1, pt2, qt1):
			return 1
		if o2 == 0 and self.onSegment(pt1, qt2, qt1):
			return 1
		if o3 == 0 and self.onSegment(pt2, pt1, qt2):
			return 1
		if o4 == 4 and self.onSegment(pt2, qt1, qt2):
			return 1
		return 0

	def onSegment(self, p, q, r):
		if q.x >= min(p.x, r.x) and q.x <= max(p.x, r.x) and (q.y >= min(p.y, r.y)) and (q.y <= max(p.y, r.y)):
			return True
		return False

	def orientation(self, p, q, r):
		val = float(q.y - p.y) * (r.x - q.x) - float(q.x - p.x) * (r.y - q.y)
		if val > 0:
			return 1
		elif val < 0:
			return 2
		else:
			return 0


class Solution:

	def doIntersect(self, p1, q1, p2, q2):

		def slope(p1, p2):
			return (p2[1] - p1[1]) / (p2[0] - p1[0])

		def onPoint(p1, p2, p3):
			x1 = p1[0]
			x2 = p2[0]
			x3 = p3[0]
			y1 = p1[1]
			y2 = p2[1]
			y3 = p3[1]
			if x3 <= max(x1, x2) and x3 >= min(x1, x2) and (y3 <= max(y1, y2)) and (y3 >= min(y1, y2)):
				return True
			return False

		def orientation(p1, p2, p3):
			x1 = p1[0]
			x2 = p2[0]
			x3 = p3[0]
			y1 = p1[1]
			y2 = p2[1]
			y3 = p3[1]
			diff = (y2 - y1) * (x3 - x2) - (y3 - y2) * (x2 - x1)
			if diff > 0:
				return 1
			elif diff == 0:
				return 0
			else:
				return -1
		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 1
		x1 = p1[0]
		x2 = p2[0]
		x3 = q1[0]
		x4 = q2[0]
		if o1 == 0 and onPoint(p1, q1, p2):
			return 1
		elif o2 == 0 and onPoint(p1, q1, q2):
			return 1
		elif o3 == 0 and onPoint(p2, q2, p1):
			return 1
		elif o4 == 0 and onPoint(p2, q2, q1):
			return 1
		return 0


class Solution:

	def doIntersect(self, p1, q1, p2, q2):

		def onSegment(p, q, r):
			if 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])):
				return 1
			return 0

		def orientation(p, q, r):
			intersect = float(q[1] - p[1]) * (r[0] - q[0]) - float(r[1] - q[1]) * (q[0] - p[0])
			if intersect > 0:
				return 1
			elif intersect < 0:
				return 2
			else:
				return 0
		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 1
		if o2 == 0 and onSegment(p1, q2, q1):
			return 1
		if o3 == 0 and onSegment(p2, p1, q2):
			return 1
		if o4 == 0 and onSegment(p2, q1, q2):
			return 1
		if o1 == 0 and onSegment(p1, p2, q1):
			return 1
		return 0


class Solution:

	def doIntersect(self, p1, q1, p2, q2):

		def collide(p, q, r):
			if (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])):
				return 1
			return 0

		def orientation(p, q, r):
			val = (r[0] - q[0]) * (p[1] - q[1]) - (r[1] - q[1]) * (p[0] - q[0])
			if val == 0:
				return 0
			elif val > 0:
				return 1
			else:
				return 2
		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 1
		if o2 == 0 and collide(p1, q2, q1):
			return 1
		if o3 == 0 and collide(p2, p1, q2):
			return 1
		if o4 == 0 and collide(p2, q1, q2):
			return 1
		if o1 == 0 and collide(p1, p2, q1):
			return 1
		return 0


class Point2D:

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

class Solution:

	def doIntersect(self, p1, p2, q1, q2):

		def get_orientation(p1: Point2D, p2: Point2D, p3: Point2D) -> int:
			val = (p2.y - p1.y) * (p3.x - p2.x) - (p2.x - p1.x) * (p3.y - p2.y)
			if val > 0:
				return 1
			elif val < 0:
				return 2
			else:
				return 0

		def is_on_segment(p1: Point2D, p2: Point2D, p3: Point2D) -> bool:
			if p2.x <= max(p1.x, p3.x) and p2.x >= min(p1.x, p3.x) and (p2.y <= max(p1.y, p3.y)) and (p2.y >= min(p1.y, p3.y)):
				return True
			return False

		def is_intersect(p1: Point2D, q1: Point2D, p2: Point2D, q2: Point2D):
			o1 = get_orientation(p1, q1, p2)
			o2 = get_orientation(p1, q1, q2)
			o3 = get_orientation(p2, q2, p1)
			o4 = get_orientation(p2, q2, q1)
			if o1 != o2 and o3 != o4:
				return True
			if o1 == 0 and is_on_segment(p1, p2, q1):
				return True
			if o2 == 0 and is_on_segment(p1, q2, q1):
				return True
			if o3 == 0 and is_on_segment(p2, p1, q2):
				return True
			if o4 == 0 and is_on_segment(p2, q1, q2):
				return True
			return False
		p1 = Point2D(p1[0], p1[1])
		p2 = Point2D(p2[0], p2[1])
		q1 = Point2D(q1[0], q1[1])
		q2 = Point2D(q2[0], q2[1])
		return int(is_intersect(p1, p2, q1, q2))


def fun(x1, y1, x2, y2, x, y):
	return (y - y1) * (x1 - x2) - (y1 - y2) * (x - x1)

def check(x1, x2, y1, y2, x, y):
	if min(x1, x2) <= x <= max(x1, x2) and min(y1, y2) <= y <= max(y1, y2):
		return True
	return False

class Solution:

	def doIntersect(self, p1, q1, p2, q2):
		if p1 == q2 or p1 == p2 or q1 == q2 or (q1 == q2) or (p2 == q1):
			return 1
		elif fun(p1[0], p1[1], q1[0], q1[1], q2[0], q2[1]) * fun(p1[0], p1[1], q1[0], q1[1], p2[0], p2[1]) == 0 and fun(p2[0], p2[1], q2[0], q2[1], q1[0], q1[1]) * fun(p2[0], p2[1], q2[0], q2[1], p1[0], p1[1]) == 0:
			if check(p1[0], q1[0], p1[1], q1[1], p2[0], p2[1]) or check(p1[0], q1[0], p1[1], q1[1], q2[0], q2[1]) or check(p2[0], q2[0], p2[1], q2[1], p1[0], p1[1]) or check(p2[0], q2[0], p2[1], q2[1], q1[0], q1[1]):
				return 1
			else:
				return 0
		if fun(p1[0], p1[1], q1[0], q1[1], q2[0], q2[1]) * fun(p1[0], p1[1], q1[0], q1[1], p2[0], p2[1]) <= 0 and fun(p2[0], p2[1], q2[0], q2[1], q1[0], q1[1]) * fun(p2[0], p2[1], q2[0], q2[1], p1[0], p1[1]) <= 0:
			return 1
		return 0


class Solution:

	def orient(self, a, b, c):
		x = (b[1] - a[1]) * (c[0] - b[0]) - (b[0] - a[0]) * (c[1] - b[1])
		if x == 0:
			return 0
		elif x > 0:
			return 1
		return 2

	def projection(self, a, b, c, d):
		if a > b:
			temp = a
			a = b
			b = temp
		if c > d:
			temp = c
			c = d
			d = temp
		if max(a, c) <= min(b, d):
			return 1
		return 0

	def doIntersect(self, p1, q1, p2, q2):
		o1 = self.orient(p1, q1, p2)
		o2 = self.orient(p1, q1, q2)
		o3 = self.orient(p2, q2, p1)
		o4 = self.orient(p2, q2, q1)
		if o1 != o2 and o3 != o4:
			return 1
		if o1 == 0 and o4 == 0:
			x = self.projection(p1[0], q1[0], p2[0], q2[0])
			y = self.projection(p1[1], q1[1], p2[1], q2[1])
			return x & y
		return 0


class Solution:

	def onSegment(self, p, q, r):
		if 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])):
			return True
		return False

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

	def doIntersect(self, p1, q1, p2, q2):
		o1 = self.orientation(p1, q1, p2)
		o2 = self.orientation(p1, q1, q2)
		o3 = self.orientation(p2, q2, p1)
		o4 = self.orientation(p2, q2, q1)
		if o1 != o2 and o3 != o4:
			return 1
		if o1 == 0 and self.onSegment(p1, p2, q1):
			return 1
		if o2 == 0 and self.onSegment(p1, q2, q1):
			return 1
		if o3 == 0 and self.onSegment(p2, p1, q2):
			return 1
		if o4 == 0 and self.onSegment(p2, q1, q2):
			return 1
		return 0
import math
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		S1 = list(map(int, input().strip().split(' ')))
		S2 = list(map(int, input().strip().split(' ')))
		p1 = []
		q1 = []
		p2 = []
		q2 = []
		p1.append(S1[0])
		p1.append(S1[1])
		q1.append(S1[2])
		q1.append(S1[3])
		p2.append(S2[0])
		p2.append(S2[1])
		q2.append(S2[2])
		q2.append(S2[3])
		ob = Solution()
		ans = ob.doIntersect(p1, q1, p2, q2)
		print(ans)


def orientation(a, b, c):
	x = (b[1] - a[1]) * (c[0] - b[0]) - (c[1] - b[1]) * (b[0] - a[0])
	if x < 0:
		return 1
	elif x > 0:
		return -1
	return 0

def overlap(l, m, r):
	return m[0] <= max(l[0], r[0]) and m[0] >= min(l[0], r[0]) and (m[1] <= max(l[1], r[1])) and (m[1] >= min(l[1], r[1]))

class Solution:

	def doIntersect(self, p, q, r, s):
		pqr = orientation(p, q, r)
		pqs = orientation(p, q, s)
		rsp = orientation(r, s, p)
		rsq = orientation(r, s, q)
		if pqr != pqs and rsp != rsq:
			return 1
		if pqr == 0 and overlap(p, r, q):
			return 1
		if pqs == 0 and overlap(p, s, q):
			return 1
		if rsp == 0 and overlap(r, p, s):
			return 1
		if rsq == 0 and overlap(r, q, s):
			return 1
		return 0


class Solution:

	def doIntersect(self, p1, q1, p2, q2):
		if q1[0] != p1[0] and q2[0] != p2[0]:
			m1 = (q1[1] - p1[1]) / (q1[0] - p1[0])
			k1 = p1[1] - m1 * p1[0]
			m2 = (q2[1] - p2[1]) / (q2[0] - p2[0])
			k2 = p2[1] - m2 * p2[0]
			if m1 != m2:
				x_intersect = round((k2 - k1) / (m1 - m2), 5)
				if min(q1[0], p1[0]) <= x_intersect <= max(q1[0], p1[0]) and min(q2[0], p2[0]) <= x_intersect <= max(q2[0], p2[0]):
					return 1
			elif m1 == m2:
				if (p1[1] - p2[1]) * (p1[0] - q1[0]) != (p1[0] - p2[0]) * (p1[1] - q1[1]):
					return 0
				max_x_line_1 = max(p1[0], q1[0])
				max_x_line_2 = max(p2[0], q2[0])
				max_x = max(max_x_line_1, max_x_line_2)
				if max_x == max_x_line_1 and max_x_line_2 >= min(p1[0], q1[0]):
					return 1
				elif max_x == max_x_line_2 and max_x_line_1 >= min(p2[0], q2[0]):
					return 1
		elif q1[0] == p1[0] and q2[0] != p2[0]:
			if min(q2[0], p2[0]) <= q1[0] <= max(q2[0], p2[0]):
				m2 = (q2[1] - p2[1]) / (q2[0] - p2[0])
				y_intersect = m2 * (q1[0] - p2[0]) + p2[1]
				if min(q1[1], p1[1]) <= y_intersect <= max(q1[1], p1[1]):
					return True
		elif q2[0] == p2[0] and q1[0] != p1[0]:
			if min(q1[0], p1[0]) <= q2[0] <= max(q1[0], p1[0]):
				m1 = (q1[1] - p1[1]) / (q1[0] - p1[0])
				y_intersect = m1 * (q2[0] - p1[0]) + p1[1]
				if min(q2[1], p2[1]) <= y_intersect <= max(q2[1], p2[1]):
					return True
		elif q1[0] == q2[0]:
			max_y_line_1 = max(p1[0], q1[0])
			max_y_line_2 = max(p2[0], q2[0])
			max_y = max(max_y_line_1, max_y_line_2)
			if max_y == max_y_line_1 and max_y_line_2 >= min(p1[1], q1[1]):
				return 1
			elif max_y == max_y_line_2 and max_y_line_1 >= min(p2[1], q2[1]):
				return 1
		return 0


class Solution:

	def orient(self, p1, p2, q):
		f = (p2[1] - p1[1]) * (q[0] - p2[0]) - (q[1] - p2[1]) * (p2[0] - p1[0])
		if f == 0:
			return 0
		if f > 0:
			return 1
		else:
			return 2

	def onSegment(self, p1, p2, r):
		if r[0] >= min(p1[0], p2[0]) and r[0] <= max(p1[0], p2[0]) and (r[1] >= min(p1[1], p2[1])) and (r[1] <= max(p1[1], p2[1])):
			return True
		return False

	def doIntersect(self, p1, q1, p2, q2):
		o1 = self.orient(p1, q1, p2)
		o2 = self.orient(p1, q1, q2)
		o3 = self.orient(p2, q2, p1)
		o4 = self.orient(p2, q2, q1)
		if o1 != o2 and o3 != o4:
			return 1
		elif o1 == 0 and self.onSegment(p1, q1, p2):
			return 1
		elif o2 == 0 and self.onSegment(p1, q1, q2):
			return 1
		elif o3 == 0 and self.onSegment(p2, q2, p1):
			return 1
		elif o4 == 0 and self.onSegment(p2, q2, q1):
			return 1
		else:
			return 0


class Point:

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

def orientation(point1, point2, point3):
	res = (point2.y - point1.y) * (point3.x - point2.x) - (point3.y - point2.y) * (point2.x - point1.x)
	if res < 0:
		return 'anticlockwise'
	if res > 0:
		return 'clockwise'
	return 'colinear'

def check_projection(point1_left, point1_right, point2_left, point2_right):
	if point1_left > point1_right:
		(point1_left, point1_right) = (point1_right, point1_left)
	if point2_left > point2_right:
		(point2_left, point2_right) = (point2_right, point2_left)
	return max(point1_left, point2_left) <= min(point1_right, point2_right)

class Solution:

	def doIntersect(self, p1, q1, p2, q2):
		line1_left = Point(p1[0], p1[1])
		line1_right = Point(q1[0], q1[1])
		line2_left = Point(p2[0], p2[1])
		line2_right = Point(q2[0], q2[1])
		o1 = orientation(line1_left, line1_right, line2_left)
		o2 = orientation(line1_left, line1_right, line2_right)
		o3 = orientation(line2_left, line2_right, line1_left)
		o4 = orientation(line2_left, line2_right, line1_right)
		if o1 != o2 and o3 != o4:
			return 1
		if o1 == 'colinear' and o4 == 'colinear':
			x_proj = check_projection(line1_left.x, line1_right.x, line2_left.x, line2_right.x)
			y_proj = check_projection(line1_left.y, line1_right.y, line2_left.y, line2_right.y)
			if x_proj and y_proj:
				return 1
		return 0


class Point:

	def __init__(self, point):
		self.x = point[0]
		self.y = point[1]

class Solution:

	def orientation(self, a1, a2, b):
		a1b = Point((a1.x - b.x, a1.y - b.y))
		a2b = Point((a2.x - b.x, a2.y - b.y))
		cp = a1b.x * a2b.y - a1b.y * a2b.x
		if cp > 0:
			return 1
		elif cp < 0:
			return -1
		else:
			return 0

	def fallsin(self, a1, a2, b):
		sx = min(a1.x, a2.x)
		mx = max(a1.x, a2.x)
		sy = min(a1.y, a2.y)
		my = max(a1.y, a2.y)
		if (b.x >= sx and b.x <= mx) and (b.y >= sy and b.y <= my):
			return 1
		else:
			return 0

	def doIntersect(self, p1, q1, p2, q2):
		p1 = Point(p1)
		q1 = Point(q1)
		p2 = Point(p2)
		q2 = Point(q2)
		o_p1q1p2 = self.orientation(p1, q1, p2)
		o_p1q1q2 = self.orientation(p1, q1, q2)
		o_p2q2p1 = self.orientation(p2, q2, p1)
		o_p2q2q1 = self.orientation(p2, q2, q1)
		if o_p1q1p2 != o_p1q1q2 and o_p2q2p1 != o_p2q2q1:
			return 1
		elif o_p1q1p2 == 0 and self.fallsin(p1, q1, p2):
			return 1
		elif o_p1q1q2 == 0 and self.fallsin(p1, q1, q2):
			return 1
		elif o_p2q2p1 == 0 and self.fallsin(p2, q2, p1):
			return 1
		elif o_p2q2q1 == 0 and self.fallsin(p2, q2, q1):
			return 1
		else:
			return 0


from collections import namedtuple
from typing import Tuple
from math import inf
Point = namedtuple('Point', ['x', 'y'])

class Solution:

	def intersect(self, l1: Tuple[Point, Point], l2: Tuple[Point, Point]) -> bool:
		(p1, q1) = l1
		(p2, q2) = l2
		a = Point(q1.x - p1.x, q1.y - p1.y)
		b = Point(p2.x - q2.x, p2.y - q2.y)
		c = Point(p2.x - p1.x, p2.y - p1.y)
		det = a.x * b.y - b.x * a.y
		if det != 0:
			n1 = (b.y * c.x - b.x * c.y) / det
			n2 = (-a.y * c.x + a.x * c.y) / det
			return 0 <= n1 <= 1 and 0 <= n2 <= 1
		else:
			x_coeff = a.x / a.y if a.y else a.x / abs(a.x) * inf if a.x else None
			y_coeff = b.x / b.y if b.y else b.x / abs(b.x) * inf if b.x else None
			c_coeff = c.x / c.y if c.y else c.x / abs(c.x) * inf if c.x else None
			if x_coeff == c_coeff or y_coeff == c_coeff:
				return ((p1.x <= p2.x <= q1.x or p1.x >= p2.x >= q1.x) or (p1.x <= q2.x <= q1.x or p1.x >= q2.x >= q1.x) or (p2.x <= q1.x <= q2.x or p2.x >= p1.x >= q2.x) or (p2.x <= q1.x <= q2.x or p2.x >= q1.x >= q2.x)) and ((p1.y <= p2.y <= q1.y or p1.y >= p2.y >= q1.y) or (p1.y <= q2.y <= q1.y or p1.y >= q2.y >= q1.y) or (p2.y <= q1.y <= q2.y or p2.y >= p1.y >= q2.y) or (p2.y <= q1.y <= q2.y or p2.y >= q1.y >= q2.y))
			else:
				return False

	def doIntersect(self, p1, q1, p2, q2) -> int:
		return int(self.intersect((Point(*p1), Point(*q1)), (Point(*p2), Point(*q2))))


class Solution:

	def doIntersect(self, p1, q1, p2, q2):
		m1 = (p1[1] - q1[1]) * (p1[0] - q2[0]) - (p1[1] - q2[1]) * (p1[0] - q1[0])
		m2 = (p1[1] - q1[1]) * (p1[0] - p2[0]) - (p1[1] - p2[1]) * (p1[0] - q1[0])
		m3 = (p2[1] - q2[1]) * (p2[0] - p1[0]) - (p2[1] - p1[1]) * (p2[0] - q2[0])
		m4 = (p2[1] - q2[1]) * (p2[0] - q1[0]) - (p2[1] - q1[1]) * (p2[0] - q2[0])
		if (m1 > 0 and m2 < 0 or (m1 < 0 and m2 > 0)) and (m3 > 0 and m4 < 0 or (m3 < 0 and m4 > 0)):
			return 1
		elif m1 == 0 and q2[0] <= max(p1[0], q1[0]) and (q2[0] >= min(p1[0], q1[0])) and (q2[1] <= max(p1[1], q1[1])) and (q2[1] >= min(p1[1], q1[1])):
			return 1
		elif m2 == 0 and p2[0] <= max(p1[0], q1[0]) and (p2[0] >= min(p1[0], q1[0])) and (p2[1] <= max(p1[1], q1[1])) and (p2[1] >= min(p1[1], q1[1])):
			return 1
		elif m3 == 0 and p1[0] <= max(p2[0], q2[0]) and (p1[0] >= min(p2[0], q2[0])) and (p1[1] <= max(p2[1], q2[1])) and (p1[1] >= min(p2[1], q2[1])):
			return 1
		elif m4 == 0 and q1[0] <= max(p2[0], q2[0]) and (q1[0] >= min(p2[0], q2[0])) and (q1[1] <= max(p2[1], q2[1])) and (q1[1] >= min(p2[1], q2[1])):
			return 1
		else:
			return 0


class Solution:

	def doIntersect(self, p1, q1, p2, q2):

		def orientation(a, b, c):
			det = (b[0] - a[0]) * (c[1] - b[1]) - (b[1] - a[1]) * (c[0] - b[0])
			if det == 0:
				dir = 0
			elif det > 0:
				dir = 1
			else:
				dir = 2
			return dir

		def onSegment(a, b, c):
			if min(a[0], b[0]) <= c[0] <= max(a[0], b[0]) and min(a[1], b[1]) <= c[1] <= max(a[1], b[1]):
				return 1
			return 0
		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 1
		if o1 == 0 and onSegment(p1, q1, p2):
			return 1
		if o2 == 0 and onSegment(p1, q1, q2):
			return 1
		if o3 == 0 and onSegment(p2, q2, p1):
			return 1
		if o4 == 0 and onSegment(p2, q2, q1):
			return 1
		return 0