maximize-the-distance-between-points-on-a-square

给你一个整数 side，表示一个正方形的边长，正方形的四个角分别位于笛卡尔平面的 (0, 0) ，(0, side) ，(side, 0) 和 (side, side) 处。

同时给你一个 正整数 k 和一个二维整数数组 points，其中 points[i] = [xi, yi] 表示一个点在正方形边界上的坐标。

你需要从 points 中选择 k 个元素，使得任意两个点之间的 最小 曼哈顿距离 最大化 。

返回选定的 k 个点之间的 最小 曼哈顿距离的 最大 可能值。

两个点 (xi, yi) 和 (xj, yj) 之间的曼哈顿距离为 |xi - xj| + |yi - yj|。

示例 1：

输入： side = 2, points = [[0,2],[2,0],[2,2],[0,0]], k = 4

输出： 2

解释：

选择所有四个点。

示例 2：

输入： side = 2, points = [[0,0],[1,2],[2,0],[2,2],[2,1]], k = 4

输出： 1

解释：

选择点 (0, 0) ，(2, 0) ，(2, 2) 和 (2, 1)。

示例 3：

输入： side = 2, points = [[0,0],[0,1],[0,2],[1,2],[2,0],[2,2],[2,1]], k = 5

输出： 1

解释：

选择点 (0, 0) ，(0, 1) ，(0, 2) ，(1, 2) 和 (2, 2)。

提示：

• 1 <= side <= 109


• 4 <= points.length <= min(4 * side, 15 * 103)


• points[i] == [xi, yi]


• 输入产生方式如下：
  
  
  
  • points[i] 位于正方形的边界上。
  
  
  • 所有 points[i] 都 互不相同 。
  
  
  
  


• 4 <= k <= min(25, points.length)