3914: Minimum Diameter
Description
You are given n points on the plane. You need to delete exactly k of them (k<n) so that the diameter of the set of the remaining n-k points were as small as possible. The diameter of a set of points is the maximum pairwise distance between the points of the set. The diameter of a one point set equals zero.
The first input line contains a pair of integers n,k (2≤n≤1000, 1≤k≤30, k<n) − the numbers of points on the plane and the number of points to delete, correspondingly.
Next n lines describe the points, one per line. Each description consists of a pair of integers xi,yi (0≤xi,yi≤32000) − the coordinates of the i-th point. The given points can coincide.
Print k different space-separated integers from 1 to n − the numbers of points to delete. The points are numbered in the order, in which they are given in the input from 1 to n. You can print the numbers in any order. If there are multiple solutions, print any of them.
5 2
1 2
0 0
2 2
1 1
3 3
5 2
4 1
0 0
0 0
1 1
1 1
3