// ++++++++++++++++++++++++++++++++++++++++
// 《零基础Go语言算法实战》源码
// ++++++++++++++++++++++++++++++++++++++++
// Author:廖显东（ShirDon）
// Blog:https://www.shirdon.com/
// Gitee:https://gitee.com/shirdonl/goAlgorithms.git
// Buy link :https://item.jd.com/14101229.html
// ++++++++++++++++++++++++++++++++++++++++

package main

import "fmt"

func ClosestPair(points [][]int, K int) [][]int {
	if len(points) == K {
		return points
	}
	var v []int
	var re [][]int
	m := make(map[int]int)
	for i := 0; i < len(points); i++ {
		m[i] = points[i][0]*points[i][0] + points[i][1]*points[i][1]
		v = append(v, i)
	}
	closestUtil(m, v, 0, len(v)-1, K)
	for i := 0; i < K; i++ {
		re = append(re, points[v[i]])
	}
	return re
}

func closestUtil(m map[int]int, s []int, start, end, k int) {
	p := m[s[end]]
	l := start
	for i := start; i < end; i++ {
		if m[s[i]] < p {
			s[l], s[i] = s[i], s[l]
			l++
		}
	}
	s[l], s[end] = s[end], s[l]
	if k == l {
		return
	} else if l < k {
		closestUtil(m, s, l+1, end, k)
	} else {
		closestUtil(m, s, start, l-1, k)
	}
}

func main() {
	points := [][]int{{2, 3}, {12, 30}, {40, 50}, {5, 1}, {12, 10}, {3, 4}}
	k := 2
	res := ClosestPair(points, k)
	fmt.Println(res)
}

//$ go run interview10-1.go
//[[2 3] [3 4]]