{"trustable":false,"sections":[{"title":"","value":{"format":"HTML","content":"\u003cdiv\u003e \n \u003cp\u003e 我们假设海岸是无限延伸的直线,陆地在海岸的一边,大海在另一边。每个小岛是一个点位于大海那一片区域\u003cspan\u003e。详见图片;\u003c/span\u003e\u003c/p\u003e \n \u003cp\u003e 每一个雷达的安装位置只能够在海岸线上,只能够覆盖半径为 d \u003cspan\u003e的圆形区域。所以,如果小岛与雷达距离小于等于d才能够覆盖。\u003c/span\u003e\u003c/p\u003e \n \u003cp\u003e \u003cspan\u003e我们可以用笛卡尔积坐标系,定义海岸线是\u003c/span\u003e \u003cspan\u003e\u003cspan\u003ex轴,大海在x\u003c/span\u003e\u003c/span\u003e \u003cspan\u003e\u003cspan\u003e上方,陆地在x\u003c/span\u003e\u003c/span\u003e 轴下方,给你每个小岛在大海中的位置,并且给出雷达的覆盖范围 d ,你的任务是写一个程序,找到最少需要安装的雷达数量且能够覆盖所有的小岛。一个位置表示 \u003cspan\u003e(x,y\u003c/span\u003e \u003cspan\u003e)坐标。\u003c/span\u003e\u003c/p\u003e \n \u003cp\u003e \u003cimg src\u003d\"CDN_BASE_URL/f6ffe515205096387436c13c7449b0ed\"\u003e\u003cbr\u003e Figure A Sample Input of Radar Installations\u003c/p\u003e \n \u003cbr\u003e \u0026nbsp;\n\u003c/div\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cdiv\u003e \n \u003cspan\u003e输入是多组\u003c/span\u003e \n \u003cspan\u003e句输入;\u003c/span\u003e\n\u003c/div\u003e \n\u003cdiv\u003e \n \u003cspan\u003e每行包含两个数\u003c/span\u003e n 和 \n \u003cspan\u003ed;\u003c/span\u003e\n\u003c/div\u003e \n\u003cdiv\u003e\n n \n \u003cspan\u003e代表小岛的数量,d\u003c/span\u003e \n \u003cspan\u003e代表雷达的覆盖半径;\u003c/span\u003e\n\u003c/div\u003e \n\u003cdiv\u003e\n 接下来n行是小岛的位置,用一个二维坐标来表示\n \u003cem\u003eXi\u003c/em\u003e,\n \u003cem\u003eYi ;\u003c/em\u003e\n\u003c/div\u003e \n\u003cdiv\u003e \n \u003cspan\u003e当输入的\u003c/span\u003e n 和 d \n \u003cspan\u003e都为0,\u003c/span\u003e 程序结束。\n\u003c/div\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cp\u003e 对于每组数据输出一个答案,每个答案占一行,输出最小需要的雷达数量,如果不能够满足要求,则输出 \u003cspan\u003e-1;\u003c/span\u003e\u003c/p\u003e \n\u003cp\u003e \u003cspan\u003e\u003cspan\u003e\u003cspan\u003e输出\u003c/span\u003e格式为:\u003c/span\u003e\u003c/span\u003e详见样例输出格式。\u003c/p\u003e"}},{"title":"Sample Input","value":{"format":"HTML","content":"\u003cpre\u003e\r\n3 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"}},{"title":"Sample Output","value":{"format":"HTML","content":"\u003cpre\u003e\r\nCase 1: 2\r\nCase 2: 1\r\n\u003c/pre\u003e"}},{"title":"Hint","value":{"format":"HTML","content":"\u003cbr\u003e"}}]}