3710. Maximum Partition Factor Hard

1/**
2 * [3710] Maximum Partition Factor
3 *
4 * You are given a 2D integer array points, where points[i] = [xi, yi] represents the coordinates of the <font>i^th</font> point on the Cartesian plane.
5 * The Manhattan distance between two points points[i] = [xi, yi] and points[j] = [xj, yj] is |xi - xj| + |yi - yj|.
6 * Split the n points into exactly two non-empty groups. The partition factor of a split is the minimum Manhattan distance among all unordered pairs of points that lie in the same group.
7 * Return the maximum possible partition factor over all valid splits.
8 * Note: A group of size 1 contributes no intra-group pairs. When n = 2 (both groups size 1), there are no intra-group pairs, so define the partition factor as 0.
9 *  
10 * Example 1:
11 * <div class="example-block">
12 * Input: <span>points = [[0,0],[0,2],[2,0],[2,2]]</span>
13 * Output: <span>4</span>
14 * Explanation:
15 * We split the points into two groups: {[0, 0], [2, 2]} and {[0, 2], [2, 0]}.
16 * 
17 * 	
18 * 	In the first group, the only pair has Manhattan distance |0 - 2| + |0 - 2| = 4.
19 * 	
20 * 	
21 * 	In the second group, the only pair also has Manhattan distance |0 - 2| + |2 - 0| = 4.
22 * 	
23 * 
24 * The partition factor of this split is min(4, 4) = 4, which is maximal.
25 * </div>
26 * Example 2:
27 * <div class="example-block">
28 * Input: <span>points = [[0,0],[0,1],[10,0]]</span>
29 * Output: <span>11</span>
30 * Explanation:​​​​​​​
31 * We split the points into two groups: {[0, 1], [10, 0]} and {[0, 0]}.
32 * 
33 * 	
34 * 	In the first group, the only pair has Manhattan distance |0 - 10| + |1 - 0| = 11.
35 * 	
36 * 	
37 * 	The second group is a singleton, so it contributes no pairs.
38 * 	
39 * 
40 * The partition factor of this split is 11, which is maximal.
41 * </div>
42 *  
43 * Constraints:
44 * 
45 * 	2 <= points.length <= 500
46 * 	points[i] = [xi, yi]
47 * 	-10^8 <= xi, yi <= 10^8
48 * 
49 */
50pub struct Solution {}
51
52// problem: https://leetcode.com/problems/maximum-partition-factor/
53// discuss: https://leetcode.com/problems/maximum-partition-factor/discuss/?currentPage=1&orderBy=most_votes&query=
54
55// submission codes start here
56
57impl Solution {
58    pub fn max_partition_factor(points: Vec<Vec<i32>>) -> i32 {
59        0
60    }
61}
62
63// submission codes end
64
65#[cfg(test)]
66mod tests {
67    use super::*;
68
69    #[test]
70    fn test_3710() {
71    }
72}
73