{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"假设海岸线是一条无限直线。陆地在海岸线的一侧,海洋在另一侧。每个小岛都是位于海洋一侧的一个点。而且任何雷达安装,位于海岸线上,只能覆盖距离d,因此海中的一个岛屿可以被雷达安装覆盖,如果它们之间的距离最多为d。\n\n我们使用笛卡尔坐标系,将海岸线定义为x轴。海洋一侧在x轴上方,陆地一侧在下方。给定海中每个岛屿的位置,以及给定雷达安装的覆盖距离,您的任务是编写一个程序,找到覆盖所有岛屿所需的最小雷达安装数量。请注意,岛屿的位置由其x-y坐标表示。\n\u003cbr\u003e\n\u003ccenter\u003e\u003cimg src\u003d\"CDN_BASE_URL/f6ffe515205096387436c13c7449b0ed?v\u003d1714186803\"\u003e\n\u003cbr\u003e图示:雷达安装的示例输入\u003c/center\u003e\n\u003cbr\u003e"}},{"title":"输入","value":{"format":"HTML","content":"输入包含多个测试用例。每个案例的第一行包含两个整数n(1≤n≤1000)和d,其中n是海中岛屿的数量,d是雷达安装的覆盖距离。接下来是n行,每行包含两个整数,表示每个岛屿位置的坐标。然后是一个空行,用于分隔案例。\n\u003cbr\u003e\n输入以包含一对零的行终止"}},{"title":"输出","value":{"format":"HTML","content":"对于每个测试用例,输出一行,包含测试用例编号,后跟所需的最小雷达安装数量。\"-1\" 表示该案例无解。"}},{"title":"示例","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e3 2\r\n1 2\r\n-3 1\r\n2 1\r\n\r\n1 2\r\n0 2\r\n\r\n0 0\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003eCase 1: 2\r\nCase 2: 1\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}}]}