#P2304H. Baba's Radar

Baba's Radar

注意

本题为远端测试题,不支持较新版本的 c++ 特性,且 不支持万能头

即:请不要使用 #include <bits/stdc++.h>for-each 语句,等等。

背景

XT 爸爸发明了一个雷达,该雷达具有在特定半径内搜索岛屿的功能。

某天,DT 儿子在冒险时,意外坠机在了一个岛屿上。可是 XT 爸爸并不知道具体位置,从而 XT 爸爸打算连夜做几个雷达,来探测出附近的所有岛屿。

有趣的是,作为整个事件的第三者,你虽然不知道 DT 儿子的具体位置,但你知道所有岛屿的坐标。

好心的你,赶在 XT 爸爸做雷达前告诉了他你知道的一切。但是,你还是想知道,如果 ST 爸爸知道所有岛屿的位置,他需要至少几个雷达,才能将所有的岛屿探测到呢?

说明

为了简化问题,我们将其抽象为一个坐标系,其中 XX 轴为 ST 爸爸能放置雷达的位置,XX 轴上方是海洋,海洋中所有岛屿的位置 Pi(xi,yi)P_i(x_i, y_i) 已知。

你需要确定雷达的 最少 数量,来让所有岛屿都在雷达的覆盖范围内。

如果无法包含所有岛屿,那么令答案为 1-1

雷达的半径为已知的 rr,且雷达只能放在 XX 轴上,如下图(画的有点抽象):

image

输入格式

本题包含多组数据,但你不需要读入数据组数

对于每组数据:

第一行包含两个整数 n,rn, r,分别为 岛屿的数量 以及 雷达的探测半径。

接下来共有 nn 行,每行包含两个整数 xi,yix_i, y_i,代表第 ii 个岛屿的坐标。

注意:当你在第一行读取到 0 0 时,代表输入结束。

输出格式

对于每组测试用例,输出一行字符串代表答案。

你需要按照 Case i: x 的格式输出,其中 ii 代表当前答案为第 ii 个测试用例,xx 为求得的最少雷达数。

样例

样例输入1

3 2
1 2
-3 1
2 1

1 2
0 2

0 0

样例输出1

Case 1: 2
Case 2: 1

第一组测试用例的图解已在题面中给出。

提示

1n1031 \leq n \leq 10 ^ 3

注意本题的提交方式。