#P4080. [Wf2014]Sensor Network
[Wf2014]Sensor Network
[ICPC2014 WF] Sensor Network
题目描述
萨曼莎使用分布在亚马孙雨林的无线传感器监测环境。为了验证一个假设,她需要选出尽可能多的传感器,使得选中的任意两个传感器都能直接通信。
每个传感器在二维平面上的位置已知。两个传感器的欧几里得距离不超过 时可以直接通信。传感器不能移动,也不能新增。请找出符合要求的最大传感器集合。
输入格式
输入只有一组数据。第一行包含两个整数 (,),分别表示传感器的数量和直接通信的最大距离。
接下来 行,每行包含两个整数 (),表示第 个传感器的坐标。传感器按输入顺序从 到 编号。
输出格式
第一行输出所选传感器的最大数量。第二行输出所选传感器的编号,每个编号只输出一次。若有多组最优解,输出任意一组即可。
样例 #1
样例输入 #1
4 1
0 0
0 1
1 0
1 1
样例输出 #1
2
1 2
样例 #2
样例输入 #2
5 20
0 0
0 2
100 100
100 110
100 120
样例输出 #2
3
4 3 5