Binary Search
IntuitionFirst hint gave me the idea, otherwise I wouldn't have immediately considered a binary search.Approach
For each point, compute distance clockwise from
# Intuition
First hint gave me the idea, otherwise I wouldn't have immediately considered a binary search.

# Approach
1. For each point, compute distance clockwise from the origin.
2. Sort the distances in increasing order. The binary search later considers including each point as the starting point; thus, to deal with array wrapping just append the original vector of distances plus the perimeter of the square.
3. Perform a binary search on the maximum minimum achievable distance. Loop on each point (represented as its distance from the origin) as the starting point. Find K iterators within the sorted vector of distances which satisfy the spacing requirements set forth by the maximum minimum distance currently under consideration.

# Complexity
- Time complexity:
<!-- Add your time complexity here, e.g. $$O(n)$$ -->
~$$O(n*log(n) + log(2 * side) * n * k * log(n)))$$

- Space complexity:
<!-- Add your space complexity here, e.g. $$O(n)$$ -->
$$O(2 * n)$$ => $$O(n)$$

# Code
```cpp []
class Solution
{
public:

    long long getClockwiseDistanceFromBottomLeft(int x,
                                                 int y,
                                                 int side)
    {
        if (x == 0) { // left side of square
            return y;
        } else if (y == side) { // top side of square
            return side + x;
        } else if (x == side) { // right side of square
            return 3LL * side - y;
        }
        // bottom side of square
        return 4LL * side - x;
    }

    int maxDistance(int side, std::vector<std::vector<int>> &points, int k)
    {
        auto n = points.size();
        std::vector<long long> clockwiseDistances(n);
        for (int i = 0; auto point : points) {
            int x = point[0];
            int y = point[1];
            clockwiseDistances[i++] = getClockwiseDistanceFromBottomLeft(x,
                                                                         y,
                                                                         side);
        }
        std::sort(std::begin(clockwiseDistances),
                  std::end(clockwiseDistances));

        for (int i = 0; i < n; ++i) {
            clockwiseDistances.push_back(4LL * side + clockwiseDistances[i]);
        }

        int low = 0;
        int high = 2 * side;
        int maxMinDistance = 0;
        while (low <= high) {
            int mid = low + (high - low) / 2;
            int maxCount = 0;
            for (int i = 0; maxCount < k && i < n; ++i) {
                int count{ 0 };
                // start at the ith point
                auto itBegin = std::begin(clockwiseDistances) + i;
                auto itEnd = itBegin + n + 1;
                auto it = itBegin;
                while (count < k) {
                    auto target = *it + mid;
                    it = std::lower_bound(it,
                                          itEnd,
                                          target);
                    if (it != itEnd) {
                        ++count;
                    } else {
                        break;
                    }
                }
                maxCount = std::max(maxCount, count);
            }

            if (maxCount >= k) {
                maxMinDistance = std::max(maxMinDistance, mid);
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
        return maxMinDistance;
    }
};
```
['Binary Search', 'C++']