O(n*n) beat 100% with optimal break points
Approach
Sort points and calculate prefix sumpx := make([]int, len(points)+1)
Calculate min distance for start point (reduce processing cost)
Loop and recursive
# Approach
- Sort points and calculate prefix sum `px := make([]int, len(points)+1)`
- Calculate min distance for start point (reduce processing cost)
- Loop and recursive for processing:
    - `dp := make(map[[2]int]int)` caching for each index
    - Try to pick `k - 1` point from start  and calculate distance
        - Break if each index has better previous point 


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

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

# Code
```golang []

func getOrder(r, c, side int) int {
	if r == 0 {
		return 1
	}
	if r == side {
		return 3
	}
	if c == 0 {
		return 4
	}
	return 2
}
func maxDistance(side int, points [][]int, k int) int {
	sort.Slice(points, func(i, j int) bool {
		o1 := getOrder(points[i][0], points[i][1], side)
		o2 := getOrder(points[j][0], points[j][1], side)
		s1 := points[i][0] + points[i][1]
		s2 := points[j][0] + points[j][1]
		return o1 < o2 || (o1 == o2 && ((o1 < 3 && s1 < s2) || (o1 > 2 && s1 > s2)))
	})
	px := make([]int, len(points)+1)
	v0 := int(math.Abs(float64(points[0][0]-points[len(points)-1][0]))) + int(math.Abs(float64(points[0][1]-points[len(points)-1][1])))
	vl := 0
	for i := 1; i < len(points); i++ {
		vl += int(math.Abs(float64(points[i][0]-points[i-1][0]))) + int(math.Abs(float64(points[i][1]-points[i-1][1])))
		px[i] = vl
	}
	px[len(points)] = px[len(points)-1] + v0
	if k == len(points) {
		rsi := math.MaxInt32
		for i := 1; i < len(px); i++ {
			rsi = min(px[i]-px[i-1], rsi)
		}
		return rsi
	}
     
	ds := len(points) / k
	st := 0
    //find start value -> min distance between k point 0-ds-2*ds ....
	rs := math.MaxInt32
	for st+ds-1 < len(px) {
		rs = min(rs, px[st+ds-1]-px[st])
		st += ds
	}
	for i := 0; i <= len(points)-k; i++ {
        //stop process because start at i is the best choice
		if px[i]-px[0] > rs {
			break
		}
		dp := make(map[[2]int]int)
		j := i + 1
        //find start value after i
		if px[j] < px[i]+rs {
			j, _ = sort.Find(len(px), func(i1 int) int {
				return px[i] + rs - px[i1]
			})
		}
		for j <= len(points)-k+1 {
			mi := maxDt(j, k-1, len(points), px, dp, rs)
			mi = min(mi, px[j]-px[i])
			if mi > rs {
				rs = mi
			}
            //stop process because j++ -> mi desc
			if px[j]-px[i] > mi {
				break
			}
			j++
            //result equal maximum distance 4*side/k
            if rs == 4*side/k {
				return rs
			}
		}
		px[len(px)-1] += px[i+1] - px[i]
	}
	return rs
}
func maxDt(i, k, l int, px []int, dp map[[2]int]int, mx int) int {
	if k == 1 {
		return px[len(px)-1] - px[i]
	}
	rs, ok := dp[[2]int{k, i}]
	if ok {
		return rs
	}
	rs = mx
	j := i + 1
	if px[j] < px[i]+rs {
		j, _ = sort.Find(len(px), func(i1 int) int {
			return px[i] + rs - px[i1]
		})
	}

	for j <= l-k+1 {
		mi := maxDt(j, k-1, l, px, dp, mx)
		mi = min(mi, px[j]-px[i])
		rs = max(rs, mi)
        //stop process because j++ -> mi desc
		if px[j]-px[i] > mi {
			break
		}
		j++
	}
	dp[[2]int{k, i}] = rs
	return rs
}
```
['Go']