{"trustable":false,"sections":[{"title":"","value":{"format":"HTML","content":"\u003cdiv class\u003d\"ptx\" lang\u003d\"en-US\"\u003e假设海岸线是一条无限长的直线。陆地在海岸线的一边,海洋在另一边。每个小岛都是位于海边的一个点。任何位于滑行方向上的雷达装置只能覆盖d距离,因此,如果距离至多为d距离,则可以用半径装置覆盖海中的一个岛屿。\n我们使用笛卡尔坐标系,定义滑行是X轴。海的一面在x轴上方,陆的一面在下面。给定每个岛屿在海洋中的位置,给定雷达装置覆盖的距离,你的任务是编写一个程序来找到覆盖所有岛屿的雷达装置的最小数量。注意,岛的位置是由它的x-y坐标表示的。\n\u003cbr\u003e\u003ccenter\u003e\u003cimg src\u003d\"CDN_BASE_URL/f6ffe515205096387436c13c7449b0ed?v\u003d1625330136\"\u003e\n\u003cbr\u003eFigure A Sample Input of Radar Installations\u003c/center\u003e\n\u003cbr\u003e\n\u003cbr\u003e\u003c/div\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cdiv class\u003d\"ptx\" lang\u003d\"en-US\"\u003e输入由几个测试用例组成。每种情况的第一行包含两个整数n(1\u003c\u003dn\u003c\u003d1000)和d,其中n是海上岛屿的数量,d是雷达装置的覆盖距离。后面是n行,每行包含两个整数,表示每个岛的位置坐标。然后用一个空行来分隔案例。\n输入端由包含一对零的行终止\n\u003cbr\u003e\u003c/div\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cdiv class\u003d\"ptx\" lang\u003d\"en-US\"\u003e对于每个测试用例输出,一行由测试用例编号组成,后面是所需雷达安装的最少数量。“-1”安装意味着在这种情况下没有解决方案。\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"}}]}