#P11878. [2023年联测]距离
[2023年联测]距离
题目描述
给定平面上 个点,第 个点编号为 ,不同编号的点坐标可以相同。删去 个点,使剩余点中任意两点的最小欧氏距离尽可能大。
原题允许在目标定义中至多删 个点。由于继续删除点不会减小最近点对的距离,且保证最后至少保留两个点,评测要求输出恰好 个被删的编号。
输入格式
第一行两个整数 。接下来 行,第 行两个整数 ,表示点 的坐标。
输出格式
输出一行 个彼此不同的整数,表示删除的点的编号。若有多组最优解,输出任意一组。 时输出空行。
样例
4 2
0 0
0 1
1 1
1 0
1 3
原题另外在下发文件中提供样例 2、3、4、5。
数据范围
所有数据满足 ,,。评测比较剩余点的最小平方欧氏距离,可以用整数计算。
| 子任务 | 上界 | 上界 | 分值 |
|---|---|---|---|
| 1 | 2000 | 0 | 5 |
| 2 | 1 | ||
| 3 | 2 | ||
| 4 | 20 | 18 | |
| 5 | 200 | 10 | 10 |
| 6 | 2000 | ||
| 7 | 20 | ||
| 8 | 30 | 15 | |
| 9 | 200 | 40 | 10 |
| 10 | 2000 | 25 |