AlgorithmAndLeetCode · pull · Jun 24, 2025 · Jun 24, 2025 · Jun 24, 2025 · Jun 24, 2025
diff --git a/...ance-Between-Points-on-a-Square/3464.Maximize-the-Distance-Between-Points-on-a-Square.cpp b/...ance-Between-Points-on-a-Square/3464.Maximize-the-Distance-Between-Points-on-a-Square.cpp
@@ -0,0 +1,73 @@
+using ll = long long;
+class Solution {
+    vector<ll>arr;
+    int next[15000];
+    int n;
+    ll side;
+public:
+    ll pos(int j) {
+        if (j<n)
+            return arr[j];
+        else
+            return arr[j%n] + side*4;
+    }
+
+    bool isOK(int dist, int k) {
+        int j = 0;
+        for (int i=0; i<n; i++) {
+            while (pos(j)-arr[i]<dist)
+                j++;
+            next[i] = j;
+        }
+
+        for (int i=0; i<n; i++) {
+            int flag = true;
+            int cur = i;
+            for (int t=0; t<k-1; t++) {
+                if (cur<n)
+                    cur = next[cur];
+                else
+                    cur = next[cur%n] + n;
+                if (cur >= i+n) {
+                    flag = false;
+                    break;
+                }
+            }
+            if (pos(i)-pos(cur%n)<dist) {
+                flag =false;
+            }
+            if (flag) {
+                return true;
+            }
+        }
+        return false;
+    }
+
+
+    int maxDistance(int side, vector<vector<int>>& points, int k) {        
+        this->n = points.size();
+        this->side = side;
+        for (auto& p: points) {
+            if (p[0]==0) 
+                arr.push_back(p[1]);
+            else if (p[1]==side)
+                arr.push_back(side+p[0]);
+            else if (p[0]==side)
+                arr.push_back(2ll*side+side-p[1]);
+            else if (p[1]==0)
+                arr.push_back(3ll*side+side-p[0]);
+        }
+
+        sort(arr.begin(), arr.end());
+
+        int low = 0, high = side;
+        while (low < high) {
+            int mid = high - (high-low)/2;
+            if (isOK(mid, k)) 
+                low = mid;
+            else
+                high = mid-1;
+        }
+        return low;
+    }
+};
diff --git a/Binary_Search/3464.Maximize-the-Distance-Between-Points-on-a-Square/Readme.md b/Binary_Search/3464.Maximize-the-Distance-Between-Points-on-a-Square/Readme.md
@@ -0,0 +1,22 @@
+### 3464.Maximize-the-Distance-Between-Points-on-a-Square
+
+我们沿着原点顺时针将所有的点放入一个数组，数组元素是每个点与原点的距离（沿着边行走）。注意题目中k大于等于4，说明点和点之间的最小曼哈顿距离不可能大于side。否则四个点绕一圈，总距离就大于四倍边长了。
+
+我们可以尝试二分搜索答案。假设猜测最小间隔距离是d，那么我们可以将任意一点作为起点，以d为极限间隔找到下一个点，以此类推找到k个点。如果第k个点没有“套圈”起点，并且离起点的距离依然大于d，那么就是一个符合条件的方案。因为k很小，我们遍历所有点作为起点都尝试一遍，时间复杂度为o(nk)，加上二分搜索的框架，总的时间复杂度是可以接受。
+
+更具体的做法是，我们先用双指针，求得每个点i右边距离恰好不超过d的点next[i]。注意i的编号范围是0到n-1，如果i是接近套圈靠近原点的位置，next[i]的位置也可能会越过原点。故我们定义next[i]的范围是0到2n-1。
+
+假设我们从p开始，做k次跨度为d跳转时，应该写成这样：
+```cpp
+for (int t=0; t<k-1; t++) {
+    if (p<n)
+        p = next[p];
+    else
+        p = next[p%n] + n;
+}
+```
+即如果p已经越过原点了（即p>=n），那么它的下一个超出了next的定义域，故我们需要用`next[p%n]`。同时因为p的下一个必然也是越过原点的，故我们需要再加n。
+
+在任何时刻，如果p点套圈了当初的起点（即p>=start+n），这说明无法实现在四周分布k个点的要求（因为第k个位置与第一个位置重合）。此外，即使p没有套圈起点，但是距离与起点少于d，也是说明无法实现要求。其余的情况，都说明有解。
+
+注意，本题是一定有解的，故二分搜索的收敛解就是最优解。
diff --git a/Readme.md b/Readme.md
@@ -153,6 +153,7 @@
 [3097.Shortest-Subarray-With-OR-at-Least-K-II](https://github.com/wisdompeak/LeetCode/tree/master/Binary_Search/3097.Shortest-Subarray-With-OR-at-Least-K-II) (M)      
 [3399.Smallest-Substring-With-Identical-Characters-II](https://github.com/wisdompeak/LeetCode/tree/master/Binary_Search/3399.Smallest-Substring-With-Identical-Characters-II) (H-)      
 [3449.Maximize-the-Minimum-Game-Score](https://github.com/wisdompeak/LeetCode/tree/master/Binary_Search/3449.Maximize-the-Minimum-Game-Score) (H-)      
+[3464.Maximize-the-Distance-Between-Points-on-a-Square](https://github.com/wisdompeak/LeetCode/tree/master/Binary_Search/3464.Maximize-the-Distance-Between-Points-on-a-Square) (H)      
     * ``Find K-th Element``       
 [215.Kth-Largest-Element-in-an-Array](https://github.com/wisdompeak/LeetCode/tree/master/Binary_Search/215.Kth-Largest-Element-in-an-Array) (M)   
 [287.Find-the-Duplicate-Number](https://github.com/wisdompeak/LeetCode/tree/master/Binary_Search/287.Find-the-Duplicate-Number) (H-)