当前你的浏览器版本过低,网站已在兼容模式下运行,兼容模式仅提供最小功能支持,网站样式可能显示不正常。
请尽快升级浏览器以体验网站在线编辑、在线运行等功能。

建议使用的浏览器:

谷歌Chrome 火狐Firefox Opera浏览器 微软Edge浏览器 QQ浏览器 360浏览器 傲游浏览器

1883:Phone Cell

题目描述
Nowadays, everyone has a cellphone, or even two or three. You probably know where their name comes from. Do you? Cellphones can be moved (they are “mobile”) and they use wireless connection to static stations called BTS (Base Transceiver Station). Each BTS covers an area around it and that area is called a cell.

The Czech Technical University runs an experimental private GSM network with a BTS right on top of the building you are in just now. Since the placement of base stations is very important for the network coverage, your task is to create a program that will find the optimal position for a BTS. The program will be given coordinates of “points of interest”.The goal is to find a position that will cover the maximal number of these points. It is supposed that a BTS can cover all points that are no further than some given distance R. Therefore, the cell has a circular shape.



The picture above shows eight points of interest (little circles) and one of the possible optimal BTS positions (small triangle). For the given distance R, it is not possible to cover more than four points. Notice that the BTS does not need to be placed in an existing point of interest.
输入解释
The input consists of several scenarios. Each scenario begins with a line containing two integer numbers N and R. N is the number of points of interest, 1 ≤ N ≤ 2000. R is the maximal distance the BTS is able to cover, 0 ≤ R < 10 000. Then there are N lines, each containing two integer numbers Xi , Yi giving coordinates of the i-th point, |Xi|,|Yi| < 10 000. All points are distinct, i.e., no two of them will have the same coordinates.

The scenario is followed by one empty line and then the next scenario begins. The last one is followed by a line containing two zeros.

A point lying at the circle boundary (exactly in the distance R) is considered covered. To avoid floating-point inaccuracies, the input points will be selected in such a way that for any possible subset of points S that can be covered by a circle with the radius R + 0.001, there will always exist a circle with the radius R that also covers them.
输出解释
For each scenario, print one line containing the sentence “It is possible to cover M points.”, where M is the maximal number of points of interest that may be covered by a single BTS.
输入样例
8 2
1 2
5 3
5 4
1 4
8 2
4 5
7 5
3 3

2 100
0 100
0 -100

0 0
输出样例
It is possible to cover 4 points.
It is possible to cover 2 points.

提示
The first sample  input scenario corresponds  to the picture, providing that the  X axis aims right and Y axis down. 
来自杭电HDUOJ的附加信息
Recommend linle

该题目是Virtual Judge题目,来自 杭电HDUOJ

源链接: HDU-1883

最后修改于 2020-10-25T22:48:33+00:00 由爬虫自动更新

共提交 0

通过率 --%
时间上限 内存上限
30000/12000MS(Java/Others) 32768/32768K(Java/Others)