{"trustable":false,"sections":[{"title":"","value":{"format":"HTML","content":"\n \u003cdiv class\u003d\"ptx\" lang\u003d\"en-US\"\u003e\n 如今我们位于沿海地区,需要安装大炮,使得火力可以覆盖整个区域。海岸线可以视为是无限长的直线。陆地位于海岸线的一侧,海洋位于另一侧。海洋里有若干个岛屿,每个小岛可以视为海洋中的一个点。我们需要在海岸线上安装大炮,每个大炮智能覆盖距离d,因此海洋中的小岛被大炮安装所覆盖的条件是两者间的距离不超过 d 。\n我们将海岸线视为 x 轴。海洋的一侧位于 x 轴上方,陆地的一侧位于下方。给定海洋中每个小岛的位置(以xy坐标给出),并给定大炮的覆盖距离,你需要写程序,找出安装大炮的最少数量,使得所有的小岛都被覆盖。\n \u003ccenter\u003e\n \u003cimg SRC\u003d\"CDN_BASE_URL/f6ffe515205096387436c13c7449b0ed?v\u003d1581644643\"\u003e \n \n \u003c/center\u003e \n \u003cbr\u003e \n \u003cbr\u003e\n \u003c/div\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\n \u003cdiv class\u003d\"ptx\" lang\u003d\"en-US\"\u003e\n 输入由多个测试用例组成。每个测试用例的第一行,包含了两个整数 n (1\u003c\u003dn\u003c\u003d1000) 和 d,其中 n 是海洋中小岛的数目,d 是大炮可以覆盖的距离。接下来是 n 行,每行包含了两个整数,表示每个小岛的坐标。每组测试用例之间,以一个空行间隔。\n\n\n \u003cbr\u003e \n \u003cbr\u003e输入终止于包含两个 0 的一行。\n \u003cbr\u003e\n \u003c/div\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\n \u003cdiv class\u003d\"ptx\" lang\u003d\"en-US\"\u003e\n 对于每个测试用例,输出一行,包括测试用例的编号,以及安装大炮所需的最小数量。如果不能全部覆盖,则输出\"-1\"。\n \u003c/div\u003e"}},{"title":"Sample Input","value":{"format":"HTML","content":"\u003cpre class\u003d\"sio\"\u003e3 2\n1 2\n-3 1\n2 1\n\n1 2\n0 2\n\n0 0\n\u003c/pre\u003e"}},{"title":"Sample Output","value":{"format":"HTML","content":"\u003cpre class\u003d\"sio\"\u003eCase 1: 2\nCase 2: 1\n\u003c/pre\u003e"}}]}