3102. Minimize Manhattan Distances Hard

1/**
2 * [3102] Minimize Manhattan Distances
3 *
4 * You are given an array points representing integer coordinates of some points on a 2D plane, where points[i] = [xi, yi].
5 * The distance between two points is defined as their <span data-keyword="manhattan-distance">Manhattan distance</span>.
6 * Return the minimum possible value for maximum distance between any two points by removing exactly one point.
7 *  
8 * <strong class="example">Example 1:
9 * <div class="example-block">
10 * Input: <span class="example-io">points = [[3,10],[5,15],[10,2],[4,4]]</span>
11 * Output: <span class="example-io">12</span>
12 * Explanation:
13 * The maximum distance after removing each point is the following:
14 * 
15 * 	After removing the 0^th point the maximum distance is between points (5, 15) and (10, 2), which is |5 - 10| + |15 - 2| = 18.
16 * 	After removing the 1^st point the maximum distance is between points (3, 10) and (10, 2), which is |3 - 10| + |10 - 2| = 15.
17 * 	After removing the 2^nd point the maximum distance is between points (5, 15) and (4, 4), which is |5 - 4| + |15 - 4| = 12.
18 * 	After removing the 3^rd point the maximum distance is between points (5, 15) and (10, 2), which is |5 - 10| + |15 - 2| = 18.
19 * 
20 * 12 is the minimum possible maximum distance between any two points after removing exactly one point.
21 * </div>
22 * <strong class="example">Example 2:
23 * <div class="example-block">
24 * Input: <span class="example-io">points = [[1,1],[1,1],[1,1]]</span>
25 * Output: <span class="example-io">0</span>
26 * Explanation:
27 * Removing any of the points results in the maximum distance between any two points of 0.
28 * </div>
29 *  
30 * Constraints:
31 * 
32 * 	3 <= points.length <= 10^5
33 * 	points[i].length == 2
34 * 	1 <= points[i][0], points[i][1] <= 10^8
35 * 
36 */
37pub struct Solution {}
38
39// problem: https://leetcode.com/problems/minimize-manhattan-distances/
40// discuss: https://leetcode.com/problems/minimize-manhattan-distances/discuss/?currentPage=1&orderBy=most_votes&query=
41
42// submission codes start here
43
44impl Solution {
45    pub fn minimum_distance(points: Vec<Vec<i32>>) -> i32 {
46        0
47    }
48}
49
50// submission codes end
51
52#[cfg(test)]
53mod tests {
54    use super::*;
55
56    #[test]
57    fn test_3102() {
58    }
59}
60