Sensor Network
题意翻译
# 无线传感器网络
## 题目背景:
无线传感器网络由一个分布在环境中监测温度、声音和 压力的自主传感器组成。萨曼莎是一名致力于阿玛苏恩二氧化碳测量(ACM)项目的研究人员。在这个项目中,亚马逊雨林的无线传感器网络通过维基媒体收集环境信息。阿玛苏恩雨林储存了相当于全球十年化石燃料排放量的碳,而且在世界氧转移过程中起着至关重要的作用。由于这片森林巨大的规格,森林通过改变风和海流不仅影响了当地环境还有全球气候。ACM项目的目标是帮助科学家更好地了解地球复杂的生态系统及其对人类活动的影响。
## 题目描述:
萨曼莎有一个重要的假设,为了检验她的假设,她需要一个传感器子集,其中每对传感器都可以直接相互通信。传感器可以直接和与它最大距离在D内的任何其他传感器通信。为了保证实验要尽可能的精确,萨曼莎想选择尽可能多的传感器。因为人不能轻易走进亚马逊,所以萨曼莎不能添加新的传感器或移动目前已经到位的传感器。
因此,给出这些传感器的当前位置,她需要你来帮助她找到满足她的标准的最大子集数。为了简单起见,将每个传感器的位置表示为一个点。在二维平面中,两点之间的距离是通常的欧几里得距离。
## 输入格式 :
输入包含几个测试用例,每个测试用例如下所述。
第一行包含两个整数N和d(1<N<100和1<d<10000) n是可用传感器的数量,d是可以直接通信的传感器之间的最大距离。
传感器编号为1到N. 接下来的N行包含两个整数X和Y(-10000<=X,Y<=10000)表示传感器的坐标。
## 输出格式 :
对于每个测试用例,输出必须遵循下面的描述。
输出的第一行表示可以直接通信的传感器的最大子集的大小。
第二行输出基于其中一个最大子集(如果有多个的话)里传感器的序号。
如果存在多个子集,则其中任何一个子集都将被接受。
题目描述
[problemUrl]: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=859&page=show_problem&problem=4642
[PDF](https://uva.onlinejudge.org/external/17/p1705.pdf)