#P4080. [Wf2014]Sensor Network

    ID: 3273 传统题 2000ms 128MiB 尝试: 645 已通过: 159 难度: 8 上传者: 标签>难度分类提高+/省选-枚举与搜索组合枚举计算几何叉积平方距离比较图论二分图建模独立集Hopcroft–Karp由匹配构造最小点覆盖构造与建模补集转化CF2500鸣谢ZidaneAndMessi

[Wf2014]Sensor Network

[ICPC2014 WF] Sensor Network

题目描述

萨曼莎使用分布在亚马孙雨林的无线传感器监测环境。为了验证一个假设,她需要选出尽可能多的传感器,使得选中的任意两个传感器都能直接通信。

每个传感器在二维平面上的位置已知。两个传感器的欧几里得距离不超过 dd 时可以直接通信。传感器不能移动,也不能新增。请找出符合要求的最大传感器集合。

输入格式

输入只有一组数据。第一行包含两个整数 n,dn,d(1≤n≤1001\le n\le100,1≤d≤10 0001\le d\le10\,000),分别表示传感器的数量和直接通信的最大距离。

接下来 nn 行,每行包含两个整数 xi,yix_i,y_i(−10 000≤xi,yi≤10 000-10\,000\le x_i,y_i\le10\,000),表示第 ii 个传感器的坐标。传感器按输入顺序从 11 到 nn 编号。

输出格式

第一行输出所选传感器的最大数量。第二行输出所选传感器的编号,每个编号只输出一次。若有多组最优解,输出任意一组即可。

样例 #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