Count Hidden Ships Inside a Rectangle

# Count Hidden Ships Inside a Rectangle Ships occupy integer-coordinate points on a plane, with at most one ship at any point. Their positions are hidden. You are given the bottom-left and top-right corners of a rectangle containing at most ten ships. Implement `Solution.countShips(sea, topRight, bottomLeft)` to return the number of ships inside that rectangle, including its boundary. Use at most **400 calls** to the supplied presence API. ### Interface `Sea.hasShips(topRight, bottomLeft) -> bool` returns `True` if at least one ship lies in the specified inclusive rectangle, and `False` otherwise. A point is represented as `[x, y]`; pass the top-right corner first and the bottom-left corner second. The candidate receives only the API object and the two query corners. Ship lists in examples initialize the private mock and must not be inspected by the candidate. Query only valid rectangles with ordered corners. A query may have zero width, zero height or be a single point. ### Examples **Example 1:** Private ships are at `[[2, 1], [2, 4], [2, 6], [3, 4]]`. For `topRight = [2, 6]` and `bottomLeft = [2, 1]`, return `3`. The query is a vertical line; ships at both endpoints count, while `[3, 4]` is outside. **Example 2:** Private ships are at `[[3, 4], [6, 6]]`. For `topRight = [6, 5]` and `bottomLeft = [4, 4]`, return `0`. Neither ship lies inside the rectangle. ### Constraints - `0 <= bottomLeft[0] <= topRight[0] <= 1000` and the same inequalities hold for coordinate `1`. - The two initial corners differ, although subsequent API queries may be single points. - At most ten ships are inside the initial rectangle. Ships outside it do not contribute to the answer. - There is at most one ship at each integer point, and positions remain fixed during the call. - At most 400 calls to `hasShips` are allowed, including repeated queries. ### What a Strong Answer Covers - Count each in-range ship exactly once, including boundary points. - Handle empty regions, adjacent coordinates and rectangles that are lines. - Keep every API query valid and justify the worst-case call count. ### Follow-up Questions - What would change if multiple ships could occupy one point? - How does increasing the coordinate range or the permitted ship count affect the query budget?