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.
示例1
输入
5 2<br />1 2<br />0 0<br />2 2<br />1 1<br />3 3<br />4 1<br />0 0<br />0 0<br />1 1<br />1 1<br />
加载中...