← 返回题目列表

Codeforces · 164/D

D. 最小直径

中文机器翻译题面 查看原题

平面上有 n 个点。您需要恰好删除其中 k 个 (k < n),以便剩余 n - k 个点的集合的直径尽可能小。一组点的直径是该组点之间的最大成对距离。一点集的直径为零。

输入

第一输入行包含一对整数 n, k (2 ≤ n ≤ 1000, 1 ≤ k ≤ 30, k < n) — 相应地,平面上的点数和要删除的点的数量。

接下来 n 行描述这些点,每行一个。每个描述由一对整数 xi, yi (0 ≤ xi, yi ≤ 32000) 组成——第 i 个点的坐标。给定的点可以重合。

输出

打印 k 个不同的空格分隔整数(从 1 到 n)——要删除的点数。这些点按照输入中给出的顺序编号,从 1 到 n。您可以按任何顺序打印数字。如果有多个解决方案,请打印其中任何一个。

示例

输入 #1

5 2
1 2
0 0
2 2
1 1
3 3

输出 #1

5 2

输入 #2

4 1
0 0
0 0
1 1
1 1

输出 #2

3