3464. Maximize the Distance Between Points on a Square Hard

1/**
2 * [3464] Maximize the Distance Between Points on a Square
3 *
4 * You are given an integer <font face="monospace">side</font>, representing the edge length of a square with corners at (0, 0), (0, side), (side, 0), and (side, side) on a Cartesian plane.
5 * You are also given a positive integer k and a 2D integer array points, where points[i] = [xi, yi] represents the coordinate of a point lying on the boundary of the square.
6 * You need to select k elements among points such that the minimum Manhattan distance between any two points is maximized.
7 * Return the maximum possible minimum Manhattan distance between the selected k points.
8 * The Manhattan Distance between two cells (xi, yi) and (xj, yj) is |xi - xj| + |yi - yj|.
9 *  
10 * <strong class="example">Example 1:
11 * <div class="example-block">
12 * Input: <span class="example-io">side = 2, points = [[0,2],[2,0],[2,2],[0,0]], k = 4</span>
13 * Output: <span class="example-io">2</span>
14 * Explanation:
15 * <img alt="" src="https://assets.leetcode.com/uploads/2025/01/28/4080_example0_revised.png" style="width: 200px; height: 200px;" />
16 * Select all four points.
17 * </div>
18 * <strong class="example">Example 2:
19 * <div class="example-block">
20 * Input: <span class="example-io">side = 2, points = [[0,0],[1,2],[2,0],[2,2],[2,1]], k = 4</span>
21 * Output: <span class="example-io">1</span>
22 * Explanation:
23 * <img alt="" src="https://assets.leetcode.com/uploads/2025/01/28/4080_example1_revised.png" style="width: 211px; height: 200px;" />
24 * Select the points (0, 0), (2, 0), (2, 2), and (2, 1).
25 * </div>
26 * <strong class="example">Example 3:
27 * <div class="example-block">
28 * Input: <span class="example-io">side = 2, points = [[0,0],[0,1],[0,2],[1,2],[2,0],[2,2],[2,1]], k = 5</span>
29 * Output: <span class="example-io">1</span>
30 * Explanation:
31 * <img alt="" src="https://assets.leetcode.com/uploads/2025/01/28/4080_example2_revised.png" style="width: 200px; height: 200px;" />
32 * Select the points (0, 0), (0, 1), (0, 2), (1, 2), and (2, 2).
33 * </div>
34 *  
35 * Constraints:
36 * 
37 * 	1 <= side <= 10^9
38 * 	4 <= points.length <= min(4 * side, 15 * 10^3)
39 * 	points[i] == [xi, yi]
40 * 	The input is generated such that:
41 * 	
42 * 		points[i] lies on the boundary of the square.
43 * 		All points[i] are unique.
44 * 	
45 * 	
46 * 	4 <= k <= min(25, points.length)
47 * 
48 */
49pub struct Solution {}
50
51// problem: https://leetcode.com/problems/maximize-the-distance-between-points-on-a-square/
52// discuss: https://leetcode.com/problems/maximize-the-distance-between-points-on-a-square/discuss/?currentPage=1&orderBy=most_votes&query=
53
54// submission codes start here
55
56impl Solution {
57    pub fn max_distance(side: i32, points: Vec<Vec<i32>>, k: i32) -> i32 {
58        0
59    }
60}
61
62// submission codes end
63
64#[cfg(test)]
65mod tests {
66    use super::*;
67
68    #[test]
69    fn test_3464() {
70    }
71}
72