Maximize the Distance Between Points on a Square
class Solution {public:int maxDistance(int side, vector<vector>& points, int k) {int n = points.size();// Center of the square for angular sortingdouble cx = si
class Solution {
public:
    int maxDistance(int side, vector<vector<int>>& points, int k) {
        int n = points.size();
        // Center of the square for angular sorting
        double cx = side / 2.0, cy = side / 2.0;

        // Sort points by polar angle around the center (clockwise)
        sort(points.begin(), points.end(), [&](const vector<int>& a, const vector<int>& b) {
            return atan2(a[1] - cy, a[0] - cx) > atan2(b[1] - cy, b[0] - cx);
        });

        // Lambda to compute Manhattan distance between points i and j
        auto md = [&](int i, int j) -> int {
            return abs(points[i][0] - points[j][0]) + abs(points[i][1] - points[j][1]);
        };

        // Lambda to find the next point after index i with distance >= mid
        auto get_next = [&](int i, int mid) -> int {
            int base = i % n; // Current point index in circular array
            int lo = i + 1, hi = i + n - 1; // Range to search (one full loop)

            // First binary search to find the "peak" where distance stops increasing
            while (lo < hi) {
                int m = (lo + hi + 1) / 2;
                int d1 = abs(points[base][0] - points[((m - 1) % n)][0]) + 
                         abs(points[base][1] - points[((m - 1) % n)][1]);
                int d2 = abs(points[base][0] - points[(m % n)][0]) + 
                         abs(points[base][1] - points[(m % n)][1]);
                if (d1 < d2) lo = m; // Distance increases, search right
                else hi = m - 1;     // Distance decreases, search left
            }
            int peak = lo; // Point where distance peaks

            // Search left of peak for the first point with distance >= mid
            int candidate1 = -1;
            int lo1 = i + 1, hi1 = peak;
            while (lo1 <= hi1) {
                int m = (lo1 + hi1) / 2;
                int d = abs(points[base][0] - points[(m % n)][0]) + 
                        abs(points[base][1] - points[(m % n)][1]);
                if (d >= mid) { candidate1 = m; hi1 = m - 1; } // Found valid, search smaller index
                else lo1 = m + 1;
            }

            // Search right of peak for the first point with distance >= mid
            int candidate2 = -1;
            int lo2 = peak, hi2 = i + n - 1;
            while (lo2 <= hi2) {
                int m = (lo2 + hi2) / 2;
                int d = abs(points[base][0] - points[(m % n)][0]) + 
                        abs(points[base][1] - points[(m % n)][1]);
                if (d >= mid) { candidate2 = m; hi2 = m - 1; } // Found valid, search smaller index
                else lo2 = m + 1;
            }

            // Return the earliest valid next point, or -1 if none found
            if (candidate1 == -1 && candidate2 == -1) return -1;
            if (candidate1 == -1) return candidate2;
            if (candidate2 == -1) return candidate1;
            return candidate1 < candidate2 ? candidate1 : candidate2;
        };

        // Lambda to check if k points can be selected with min distance mid
        auto can = [&](int mid) -> bool {
            for (int i = 0; i < n; i++) { // Try each point as starting point
                int cnt = 1, cur = i; // Count starts at 1 with current point
                bool valid = true;
                while (cnt < k) {
                    int nxt = get_next(cur, mid); // Get next point at least mid away
                    if (nxt == -1 || nxt >= i + n) { // No valid next point or exceeded one loop
                        valid = false;
                        break;
                    }
                    cur = nxt;
                    cnt++;
                }
                // Check if k points selected and wrap-around distance is >= mid
                if (valid && cnt == k && md(cur % n, i % n) >= mid) return true;
            }
            return false;
        };

        // Binary search for the maximum feasible distance
        long long lo_val = 0, hi_val = 2LL * side, ans = 0;
        while (lo_val <= hi_val) {
            long long mid = (lo_val + hi_val) / 2;
            if (can((int)mid)) { // If feasible, try larger distance
                ans = mid;
                lo_val = mid + 1;
            } else { // Otherwise, try smaller distance
                hi_val = mid - 1;
            }
        }
        return (int)ans;
    }
};
['C++']