Rectangle Coverage — Maximum Points - Deutsche Bank Online Assessment IIT BHU

Problem Preview

"You are given a set of **N distinct points** on a two-dimensional coordinate plane along with an even integer `perimeter`. Your task is to position a rectangle so that it contains the **largest possible number of given points**. A point is considered covered when it is either: * strictly inside the rectangle, or * located directly on one of its four sides. The rectangle must be **axis-aligned**, meaning its sides cannot be rotated and must remain parallel to the coordinate axes. The total length of all four sides must be exactly `perimeter`. --- ## Rectangle Dimensions Let the rectangle have: * width = `W` * height = `H` Its perimeter is: ```text 2 × W + 2 × H = perimeter ``` or equivalently: ```text W + H = perimeter / 2 ``` For example, when: ```text perimeter = 10 ``` the available `(width, height)` combinations are: ```text (1, 4) (2, 3) (3, 2) (4, 1) ``` The rectangle can be translated to any position on the plane. --- ## Required Function The following structure is provided: ```cpp struct Point2D { int x; int y; }; ``` Implement the function: ```cpp int solution(vector<Point2D> &points, int perimeter); ``` The function must return the **highest number of input points that can simultaneously lie inside or on the boundary of a valid rectangle**. --- # Examples ## Example 1 ### Input ```text points = [ (1, 1), (-1, -1), (-2, 2), (2, 0) ] perimeter = 10 ``` ### Output ```text 3 ``` ### Explanation A rectangle with dimensions `3 × 2` has perimeter: ```text 2 × (3 + 2) = 10 ``` It can be positioned to contain the following three points: ```text (-1, -1) (1, 1) (2, 0) ``` Hence, the maximum number of covered points is **3**. ### Illustration ```text y ↑ 2 ● (-2,2) 1 ┌──────────────● (1,1) │ 0 │ ● (2,0) │ -1 ● (-1,-1) └────────────── └────────────────────────→ x ``` --- ## Example 2 ### Input ```text points = [ (0, 0), (-1, 3), (2, -2), (-2, -1), (-2, 0), (2, 3), (1, -1), (0, 1), (2, 0) ] perimeter = 14 ``` ### Output ```text 7 ``` ### Explanation A valid rectangle with dimensions: ```text 4 × 3 ``` has perimeter: ```text 2 × (4 + 3) = 14 ``` By choosing an appropriate position for this rectangle, **7 of the 9 points** can be covered. Thus, the maximum possible number of covered points is **7**. ### Illustration ```text y ↑ 3 ● (-1,3) ● (2,3) 2 1 ● (0,1) 0 ● (-2,0) ● (0,0) ● (2,0) -1 ● (-2,-1) ● (1,-1) -2 ● (2,-2) └──────────────────────────→ x ``` --- # Constraints * `N` is between `1` and `40`. * Every `x` coordinate is between `-10` and `10`. * Every `y` coordinate is between `-10` and `10`. * All points are different. * `perimeter` is an even integer between `4` and `40`. The primary requirement is **correctness**; the input limits are small enough that an exhaustive search over possible rectangle dimensions and placements is acceptable. ---"