Minimum Diameter

题意翻译

# 题目描述 你在图上有N个点。你需要完全删除其中的k（k<n）个点，以便使剩余的n-k个点的直径尽可能小。一组点的直径是该组点中每两个点之间的最大成对距离。一个点的直径等于零。 # 输入输出格式 ### 输入格式 第一行包含一对整数n,k（2<=n<=1000,1<=k<=30,k<n）n代表平面上的点的数目，k代表要删除的点的数目。 接下来的n行描述点，每行描述一个点。每行包含一对整数x，y（0<=x，y<=32000）表示第i点的坐标。可能有重点。 ### 输出格式 输出k个以空间分隔的，要删除的点的序号（输入中的点是按从1到n的顺序编号的）。你可以按任意顺序输出。如果有多个解决方案，输出任意一种方案。

题目描述

You are given $ n $ points on the plane. You need to delete exactly $ k $ of them $ (k&lt;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&lt;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 $ x_{i},y_{i} $ ( $ 0<=x_{i},y_{i}<=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
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