// list of points (x, y)
func swap(list [][]int, i int, j int) {
    temp := list[i]
    list[i] = list[j]
    list[j] = temp
}

// point (x, y)
func area(point []int) int {
    return point[0]*point[0] + point[1]*point[1]
}

func kClosest(list [][]int, k int) [][]int {
    left := 0
    right := len(list)-1
    divPoint := len(list)
    
    for divPoint != k {
        divPoint = partition(list, left, right)
        
        if divPoint < k {
            left = divPoint
        } else {
            right = divPoint - 1
        }
    }
    
    return list[:k]
}

// return new division point
func partition(list [][]int, left int, right int) int {
    // the current middle point (between x and y)
    markerPoint := list[left + (right-left)/2]

    // larger area = father from the origin
    markerArea := area(markerPoint)
    
    // iterate until there is no points in between left and right
    for left < right {
        leftPointArea := area(list[left])
        
        // left point distance >= middle point distance
        if (leftPointArea >= markerArea) {
            // swap value for start and end
            swap(list, left, right)
            right = right - 1
        } else {
            // if markerArea closer to the origin, move start (left point) to the right
            left = left + 1
        }
    }
    
    // left point on after the end of left range
    if area(list[left]) < markerArea {
        left = left + 1
    }
    
    return left
}