Maximum Minimum Manhattan Distance on a Square Boundary

### Problem A square has corners `(0,0)`, `(0,side)`, `(side,0)`, and `(side,side)`. You are given distinct integer-coordinate points on its boundary and an integer `k`. Select exactly `k` of the given points. For that selection, consider the Manhattan distance between every pair: ```text distance((x1,y1), (x2,y2)) = |x1 - x2| + |y1 - y2| ``` Return the greatest possible value of the **minimum** pairwise distance. Select only from the supplied points, and return the distance rather than the selected points. ```cpp class Solution { public: int maxDistance(int side, vector<vector<int>>& points, int k); }; ``` ### Examples **Example 1:** ```text Input: side = 4, points = [[0,0],[0,4],[4,4],[4,0],[0,2]], k = 4 Output: 4 Explanation: Choose the four corners. Adjacent corners are distance 4 and opposite corners are distance 8, so their minimum is 4. No choice of four boundary points can have a larger minimum distance. ``` **Example 2:** ```text Input: side = 3, points = [[0,0],[0,3],[3,3],[3,0],[0,1],[1,3]], k = 5 Output: 1 Explanation: The disjoint pairs {(0,0),(0,1)} and {(0,3),(1,3)} each have distance 1. Selecting five of the six points leaves at least one whole pair selected, so the minimum cannot exceed 1. Distinct integer points always have distance at least 1, making that bound attainable. ``` ### Constraints - `1 <= side <= 10^9`. - `4 <= points.length <= min(4 * side, 15000)`. - Each point contains two integer coordinates and lies on the square's boundary. - All supplied points are unique. - `4 <= k <= min(25, points.length)`. ### Clarifying Questions - Is the distance Euclidean or distance traveled along the boundary? Neither. Use the stated Manhattan distance. - May new points be placed anywhere on the boundary? No, choose from `points`. - Is the objective the sum of distances? No, maximize the smallest distance among all selected pairs. - Are the points already ordered around the square? No ordering is guaranteed. ### What a Strong Answer Covers - Preserves the exact selection count and the Manhattan distance between every selected pair. - Justifies both the validity and optimality of the returned minimum distance. - Handles corners and points on the same, adjacent, or opposite sides of the square. - Supports the full point count and large coordinates with suitable arithmetic and complexity bounds. ### Follow-up Questions - Can adding another available boundary point reduce the best achievable minimum distance when `k` stays fixed? - Where does the lower bound `k >= 4` matter in a proof? ```hint Use the selection-count bound carefully Ordering points around the perimeter may help test a proposed minimum distance. First establish which distance thresholds need consideration and when boundary separation can certify Manhattan separation. ```