Binary search, k >= 4 implies ans <= side & square perimeter can be unfolded as a line 
IntuitionApproachComplexity
Time complexity:

Space complexity:
Code
# Intuition
<!-- Describe your first thoughts on how to solve this problem. -->

# Approach
<!-- Describe your approach to solving the problem. -->

# Complexity
- Time complexity:
<!-- Add your time complexity here, e.g. $$O(n)$$ -->

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

# Code
```python3 []
class Solution:
    def maxDistance(self, side: int, points: List[List[int]], k: int) -> int:
        A = []
        for x, y in points:
            if y == 0:
                d = x
            elif x == side:
                d = side + y
            elif y == side:
                d = 2 * side + (side - x)
            else:
                d = 3 * side + (side - y)
            A.append(d)
        A.sort()

        def check(d):
            n = len(A)
            i0 = bisect.bisect_left(A, A[0] + d)  
            #Exactly one point i in the range 0 <= i < i0 must be selected 
            if n - i0 < k - 1:
                return False
            for i in range(i0):
                count = 1
                pre = A[i] # i is the first point selected
                for _ in range(k - 1):
                    j = bisect.bisect_left(A, pre + d)
                    if j < n and (4 * side - A[j]) + A[i] >= d:
                        pre = A[j]
                        count += 1
                    else:
                        break #Fail
                if count == k:
                    return True
            return False

        lo, hi, ans = 1, side, 1 # k >= 4 implies ans <= side & distinct points implies ans >= 1
        while lo <= hi:
            mid = (lo + hi) // 2
            if check(mid):
                ans = mid
                lo = mid + 1
            else:
                hi = mid - 1
        return ans

```
['Python3']