ENG  RUSTimus Online Judge
Online Judge
Online contests
About Online Judge
Frequently asked questions
Site news
Problem set
Submit solution
Judge status
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests

USU Open Personal Contest 2011

About     Problems     Submit solution     Judge status     Standings
Contest is over

E. Ifrit Bomber

Time limit: 0.5 second
Memory limit: 64 MB
In the six years that passed since the first experimental genie bombardments, Pitirim Schwartz has made considerable advance. His latest invention is an ifrit bottle, which has been developed especially for bombing large cities. Each ifrit from such a bottle ruins everything within a radius of r miles from the impact point. Only a few ifrit bottles are needed to demolish all n large cities of a neighboring country… Alas, Pitirim has very few ifrit bottles, so he has asked programmer Privalov to compute the minimal number of bottles needed for the destruction of all the cities.
For the convenience of aiming, the bottles can only be dropped exactly on cities. The radius of destruction is so large that cities can be regarded as points of the plane. When an ifrit bottle is dropped, any city within or on the border of the destruction zone is demolished.


In the first line you are given integers n and r (1 ≤ n ≤ 30; 1 ≤ r ≤ 1000). The i-th of the following n lines contains the coordinates of the i-th city; these are two integers in the range from 0 to 1000.


In the first line output the minimal number of bottles needed to demolish all the cities. In the following line give the numbers of the cities on which the bottles should be dropped. The numbers must be separated with a space. If there are many ways to drop the bottles you can output any of them.


4 50
10 10
500 500
501 501
999 999
1 3 4
Problem Author: Igor Andrianov
Problem Source: XII USU Open Personal Contest (March 19, 2011)
To submit the solution for this problem go to the Problem set: 1824. Ifrit Bomber