#P11878. [2023年联测]距离

    ID: 11029 传统题 1000ms 888MiB 尝试: 1 已通过: 1 难度: 8 上传者: 标签>CF2500提高+/省选-二分答案顶点覆盖回溯搜索可行性剪枝搜索顺序优化链表回滚维护状态平方距离比较

[2023年联测]距离

题目描述

给定平面上 nn 个点,第 ii 个点编号为 ii,不同编号的点坐标可以相同。删去 kk 个点,使剩余点中任意两点的最小欧氏距离尽可能大。

原题允许在目标定义中至多删 kk 个点。由于继续删除点不会减小最近点对的距离,且保证最后至少保留两个点,评测要求输出恰好 kk 个被删的编号。

输入格式

第一行两个整数 n,kn,k。接下来 nn 行,第 ii 行两个整数 xi,yix_i,y_i,表示点 ii 的坐标。

输出格式

输出一行 kk 个彼此不同的整数,表示删除的点的编号。若有多组最优解,输出任意一组。k=0k=0 时输出空行。

样例

4 2
0 0
0 1
1 1
1 0
1 3

原题另外在下发文件中提供样例 2、3、4、5。

数据范围

所有数据满足 2≤n≤20002\le n\le2000,0≤k≤min⁡(n−2,40)0\le k\le\min(n-2,40),∣xi∣,∣yi∣≤108|x_i|,|y_i|\le10^8。评测比较剩余点的最小平方欧氏距离,可以用整数计算。

子任务 nn 上界 kk 上界 分值
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

原 PDF 题面