300863: CF164D. Minimum Diameter
Memory Limit:256 MB
Time Limit:1 S
Judge Style:Text Compare
Creator:
Submit:0
Solved:0
Description
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<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 $ 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