
def on_segment(p, q, r):
    # Given three colinear points p, q, r, the function checks if
    # point q lies on line segment 'pr'
    if q.x <= max(p.x, r.x) and q.x >= min(p.x, r.x) and \
       q.y <= max(p.y, r.y) and q.y >= min(p.y, r.y):
        return True
    return False


def intersect(a, b, c, d):
    # Return true if line segments ab and cd intersect
    def ccw(a, b, c):
        return (c.y - a.y) * (b.x - a.x) > (b.y - a.y) * (c.x - a.x)
    return ccw(a, c, d) != ccw(b, c, d) and ccw(a, b, c) != ccw(a, b, d)


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

    # See https://www.geeksforgeeks.org/orientation-3-ordered-points/
    # for details of below formula.
    val = (q.y - p.y) * (r.x - q.x) - (q.x - p.x) * (r.y - q.y)

    if val == 0:
        return 0  # colinear

    # clock or counterclock wise
    if val > 0:
        return 1
    return 2


def in_square(p1, x_min, x_max, y_min, y_max):
    if p1.x < x_min or p1.x > x_max:
        return False
    if p1.y < y_min or p1.y > y_max:
        return False
    return True


def in_circle(p1, p_center, radius):
    return (p1.x - p_center.x)**2 + (p1.y - p_center.y)**2 < radius**2


def do_intersect(p1, q1, p2, q2):
    # The main function that returns true if line segment 'p1q1'
    # and 'p2q2' intersect.
    # Find the four orientations needed for general and
    # special cases
    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 q2 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

    return False
