P6900 [ICPC 2014 WF] Sensor Network

一个无线传感器网络由分散在环境中的自主传感器组成，它们监测温度、声音和压力等条件。 Samantha 是一名研究人员，正在从事亚马逊二氧化碳测量（ACM）项目。在该项目中，亚马逊雨林中的无线传感器网络收集环境信息。亚马逊雨林储存的碳量相当于全球化石燃料排放量的十年，并在全球氧气传输过程中发挥着关键作用。由于这片森林的巨大规模，森林的变化不仅影响当地环境，还通过改变风和洋流模式影响全球气候。ACM 项目的目标是帮助科学家更好地理解地球复杂的生态系统以及人类活动的影响。 Samantha 有一个重要的假设，为了验证她的假设，她需要找到一个传感器子集，其中每对传感器可以直接相互通信。一个传感器可以与距离不超过 $d$ 的任何其他传感器直接通信。为了使她的实验尽可能准确，Samantha 希望选择尽可能多的传感器。 由于不能简单地进入亚马逊，Samantha 不能添加新的传感器或移动当前的位置。因此，给定传感器的当前位置，她需要你的帮助来找到满足她标准的最大子集。为简单起见，将每个传感器的位置表示为二维平面上的一个点，两个点之间的距离为通常的欧几里得距离。

输入由一个测试用例组成。第一行包含两个整数 $n$ 和 $d$（$1 \le n \le 100$ 且 $1 \le d \le 10\, 000$），其中 $n$ 是可用传感器的数量，$d$ 是可以直接通信的传感器之间的最大距离。传感器编号为 $1$ 到 $n$。接下来的 $n$ 行中的每一行包含两个整数 $x$ 和 $y$（$-10\, 000\le x, y \le 10\, 000$），表示传感器的坐标，从第一个传感器开始。

输出一个最大传感器子集，其中每对传感器可以直接通信。输出的第一行应为子集的大小。第二行应为子集中传感器的（从 1 开始的）索引。如果有多个这样的子集，任何一个都将被接受。

时间限制：2000 毫秒，内存限制：1048576 kB。 国际大学生程序设计竞赛（ACM-ICPC）世界总决赛 2014。 题面翻译由 ChatGPT-4o 提供。