Bisect Squares

16.13 Bisect Squares: Given two squares on a two-dimensional plane, find a line that would cut these two squares in half. Assume that the top and the bottom sides of the square run parallel to the x-axis.

• The idea of this problem is very simple: Simply define that line goes through the center of both squares.

  • Defining this by hand is a bit tedious and mechanic, so we'll have to make sure to have a careful and solid design.

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

class Line:
    def __init__(self, start : Point, end : Point):
        self.start = start
        self.end = end

class Square:
    def __init__(self, left,  top, size):
        self.left = left
        self.top = top
        self.right = left + size
        self.bottom = top + size
        self.size = size

    def middle(self) -> Point:
        return Point((self.left + self.right)/2, (self.top + self.bottom)/2)

   def dir(self, x1, x2) -> int:
        if x1 < x2:
            return -1
        else:
            return 1

    def extend(self, mid1, mid2, size) -> Point:
        xdir = self.dir(mid1.x, mid2.x)
        ydir = self.dir(mid1.y, mid2.y)

        if mid1.x == mid2.x:
            return Point(mid1.x, mid1.y +ydir*size/2);

        slope = (mid1.y- mid2.y)/ (mid1.x - mid2.x)

        x1 = 0
        y1 = 0

        if abs(slope) == 1 :
            x1 = mid1.x + (xdir*size)/2
            y1 = mid1.y + (ydir*size)/2
        elif abs(slope) < 1:
            x1 = mid1.x + (xdir*size)/2
            y1 =slope*(x1-mid1.x) + mid1.y
        else:
            y1 = mid1.y + (ydir*size)/2
            x1= (y1 - mid1.y)/(slope + mid1.x)

        return Point(x1,y1)

def cut(me : Square, other : Square) -> Line:
    p1 = me.extend(me.middle(), other.middle(), me.size)
    p2 = me.extend(me.middle(), other.middle(), -1* me.size)
    p3 = other.extend(other.middle(), me.middle(), other.size)
    p4 = other.extend(other.middle(), me.middle(), -1* other.size)

    list = {p2,p3,p4}

    s = p1
    e = p1

    for p in list:
        if p.x < s.x or p.x==s.x and p.y < s.y:
            s = p
        elif p.x > e.x or p.x == e.x and p.y > e.y:
            e =p

    return Line(s,e)