# """

# This is Sea's API interface.

# You should not implement it, or speculate about its implementation

# """

#class Sea(object):

#    def hasShips(self, topRight: 'Point', bottomLeft: 'Point') -> bool:

#

#class Point(object):

#    def __init__(self, x: int, y: int):

#        self.x = x

#        self.y = y

class Solution(object):

    def countShips(self, sea: 'Sea', topRight: 'Point', bottomLeft: 'Point') -> int:

        if topRight.x == bottomLeft.x and topRight.y == bottomLeft.y and sea.hasShips(topRight,bottomLeft):

            return 1

        if sea.hasShips(topRight,bottomLeft):

            mid_h = (topRight.y + bottomLeft.y)//2

            mid_w = (topRight.x + bottomLeft.x)//2

            a = self.countShips(sea,Point(mid_w,topRight.y),Point(bottomLeft.x,mid_h+1)) if mid_h != topRight.y else 0

            b = self.countShips(sea,topRight,Point(mid_w+1,mid_h+1)) if mid_h != topRight.y and mid_w != topRight.x else 0

            c = self.countShips(sea,Point(mid_w,mid_h),bottomLeft)

            d = self.countShips(sea,Point(topRight.x,mid_h),Point(mid_w+1,bottomLeft.y)) if mid_w != topRight.x else 0

            return a + b + c + d

        return 0