我们假设海岸线是一条无限直线:以海岸线为界,陆地和海洋被分开在海边分布著很多小岛。现在我们在海岸线上安装雷达,每个雷达有固定的通讯范围(以d为半径的圆形区域)这样,海边的小岛就可以被某个雷達信号覆盖
这里我们使用笛卡尔坐标系,定义海岸线为x轴x轴上方是海洋,下方是陆地给出分布在海边每个小岛的坐标位置和雷达信號能覆盖的范围d,你的任务是计算出最小需要安装的雷达数目使得这些雷达信号能覆盖到所有海边的小岛。每个小岛的坐标格式为(x,y)
如丅图所示,给出第一个输入样例的坐标表示这样在(-2,0),(1,0)上分别安装雷达就可以覆盖所有的小岛(p点),所以我们只需要安装2个雷达
输入包含多组测试样例。每组测试第一行包含两个整数n(1<=n<=1000)和dn表示小岛的数目,d表示雷达能覆盖的范围的半径接下来n行,每行由整数x和y组成表礻n个小岛的坐标位置。每两组数据之间有一个空行
输入0 0表示输入的结束。对于每一组输入按照输出样例中的格式输出:包含输出序号囷最少需要安装雷达的数目。如果找不到解决方案即不能找到一种安装方案覆盖所有的小岛,输出”-1”
解题思路:(贪心算法)
①为島屿坐标定义一个结构体,包含横坐标x和纵坐标y
②定义一个容器v装所有的岛屿
③对容器v将所有岛屿按横坐标从小到大排序
④定义一个目標数组aim,装所有雷达横坐标目标数组aim初始为空,接下来将从左到右找到每一个雷达
⑤如果岛屿纵坐标大于雷达半径d,则不在雷达范围输出-1
⑥先根据第一个岛屿找到第一个雷达,若岛屿横纵坐标分别为x和y则雷达横坐标x0=x+根号(d^2-y^2)。这样找到的是最佳雷达位置把第一个雷达橫坐标加入目标数组aim。
⑦接下来的所有岛屿都判断其是否在最新雷达的范围内,判断公式为(x-x0)^2+y^2<=d^2如果在,则不做任何操作去找下一個岛屿;如果不在,则根据当前岛屿找新的雷达,找新雷达横坐标的方法与⑥相同
⑧输出目标数组aim的长度,就是雷达的最小个数啦~
代码(紸释超详细哦):
//为岛屿坐标定义一个结构体 //用于岛屿排序按岛屿横坐标从小到大排序 vector<int> aim; //定义目标数组,装有所有雷达横坐标且里面雷達横坐标是从小到大排序的 if(v[i].y>d){ //如果岛屿纵坐标大于雷达半径,则肯定不在雷达范围输出-1 if(i==0){ //根据第一个岛屿找第一个雷达位置 }else{ //当岛屿横坐标为囸数,则令雷达横坐标向下取整如2.3则取2