← 返回题目

题库练习 Minimum Diameter

← 上一题下一题 →

A8384 | $Minimum Diameter$

时间限制1s

内存限制256MB

通过 / 提交0/0

题目描述

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

输出 #1

5 2

输入 #2

输出 #2

C++ 编辑器

输入

输出