题目描述

A wireless sensor network consists of autonomous sensors scattered in an environment where they monitor conditions such as temperature, sound, and pressure.

Samantha is a researcher working on the Amazon Carbon-dioxide Measurement (ACM) project. In this project, a wireless sensor network in the Amazon rainforest gathers environmental information. The Amazon rainforest stores an amount of carbon equivalent to a decade of global fossil fuel emissions, and it plays a crucial role in the world’s oxygen-transfer processes. Because of the huge size of this forest, changes in the forest affect not only the local environment but also global climate by altering wind and ocean current patterns. The goal of the ACM project is to help scientists better understand earth’s complex ecosystems and the impact of human activities.

Samantha has an important hypothesis and to test her hypothesis, she needs to find a subset of sensors in which each pair of sensors can communicate directly with each other. A sensor can communicate directly with any other sensor having distance at most $d$ from it. In order for her experiments to be as accurate as possible, Samantha wants to choose as many sensors as possible.

As one does not simply walk into the Amazon, Samantha cannot add new sensors or move those that are currently in place. So given the current locations of the sensors, she needs your help to find the largest subset satisfying her criteria. For simplicity, represent the location of each sensor as a point in a two-dimensional plane with the distance between two points being the usual Euclidean distance.

输入格式

The input consists of a single test case. The first line contains two integers $n$ and $d$ ($1 \le n \le 100$ and $1 \le d \le 10\, 000$), where $n$ is the number of sensors available and $d$ is the maximum distance between sensors that can communicate directly. Sensors are numbered $1$ to $n$. Each of the next $n$ lines contains two integers $x$ and $y$ ($-10\, 000\le x, y \le 10\, 000$) indicating the sensor coordinates, starting with the first sensor.

输出格式

Display a maximum subset of sensors in which each pair of sensors can communicate directly. The first line of output should be the size of the subset. The second line of output should be the (one-based) indices of the sensors in the subset. If there are multiple such subsets, any one of them will be accepted.

题目大意

无线传感器网络由分散在环境中的自主传感器组成，它们监控温度、声音和压力等条件。

萨曼莎是亚马逊二氧化碳测量 (Amazon Carbon-dioxide Measurement, ACM) 项目的研究员。在这个项目中，亚马逊雨林的无线传感器网络收集环境信息。亚马逊雨林储存了相当于十年全球化石燃料排放量的碳，它在世界的氧气转移过程中扮演着至关重要的角色。由于这片森林面积巨大，森林的变化不仅会影响当地环境，还会通过改变风和洋流模式来影响全球气候。ACM 项目的目标是帮助科学家更好地了解地球复杂的生态系统和人类活动的影响。

萨曼莎有一个重要的猜想，为了验证她的猜想，她需要找到传感器的一个子集，在这些传感器中，每对传感器都可以直接相互通信。传感器可以与距离它不超过 $d$ 的任何其他传感器直接通信。为了让她的实验尽可能准确，萨曼莎希望选择尽可能多的传感器。

因为人们不能简单地走进亚马逊，萨曼莎不能添加新的传感器，也不能移动那些目前设置好的传感器。因此，给出传感器目前的位置，她需要你的帮助来找到满足她标准的最大子集。为简单起见，每个传感器的位置被表示为二维平面中的一个点，两点之间的距离为通常的欧几里德距离。

输入

第一行两个整数 $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$ 开始编号)。如果有多个满足要求的最大子集，输出任意一个均可。

4 1
0 0
0 1
1 0
1 1

2
1 2

5 20
0 0
0 2
100 100
100 110
100 120

3
4 3 5

提示

Time limit: 2000 ms, Memory limit: 1048576 kB.

International Collegiate Programming Contest (ACM-ICPC) World Finals 2014