QOJ.ac

QOJ

Limite de temps : 3.0 s Limite de mémoire : 128 MB Points totaux : 100

#16128. 电话基站

Statistiques

如今,每个人都拥有一部手机,甚至两三部。你可能知道它们名字的由来。手机是可以移动的(它们是“移动的”),并且它们使用无线连接到被称为基站(BTS,Base Transceiver Station)的固定站点。每个基站覆盖其周围的一个区域,该区域被称为小区(cell)。

捷克理工大学运行着一个实验性的私有 GSM 网络,在你目前所在的建筑顶部就有一个基站。由于基站的布局对网络覆盖至关重要,你的任务是编写一个程序,寻找基站的最佳位置。程序将给出“兴趣点”的坐标。目标是找到一个能够覆盖最多兴趣点的位置。假设基站可以覆盖所有距离其不超过给定距离 $R$ 的点。因此,小区的形状为圆形。

上图显示了八个兴趣点(小圆圈)和其中一个可能的最佳基站位置(小三角形)。对于给定的距离 $R$,不可能覆盖超过四个点。请注意,基站不需要放置在现有的兴趣点上。

输入格式

输入包含多个测试用例。每个测试用例的第一行包含两个整数 $N$ 和 $R$。$N$ 是兴趣点的数量,$1 \le N \le 2000$。$R$ 是基站能够覆盖的最大距离,$0 \le R < 10000$。接下来的 $N$ 行中,每行包含两个整数 $X_i, Y_i$,表示第 $i$ 个点的坐标,且 $|X_i|, |Y_i| < 10000$。所有点都是互不相同的,即没有两个点具有相同的坐标。

每个测试用例之后紧跟一个空行,然后开始下一个测试用例。最后一个测试用例之后是一行包含两个零。

位于圆边界上(距离恰好为 $R$)的点也被视为被覆盖。为了避免浮点数精度误差,输入的点在生成时满足以下条件:对于任何可以被半径为 $R + 0.001$ 的圆覆盖的点的子集 $S$,总是存在一个半径为 $R$ 的圆也能够覆盖它们。

输出格式

对于每个测试用例,输出一行,包含句子 "It is possible to cover M points.",其中 $M$ 是单个基站可以覆盖的最大兴趣点数量。

样例

输入样例 1

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

输出样例 1

It is possible to cover 4 points.
It is possible to cover 2 points.

说明

第一个样例输入对应的场景如上图所示,其中 $X$ 轴向右,$Y$ 轴向下。

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.