首页 > 代码库 > Poj1328 用雷达覆盖所有的岛屿
Poj1328 用雷达覆盖所有的岛屿
(此配图来自http://blog.csdn.net/zhengnanlee/article/details/9613161)
图中ABCD为海岛的位置。题目中会给出几个海岛的坐标位置,雷达覆盖半径d,问你用几个雷达可实现海岛的全部覆盖,不能就输出-1。
观察图可知:(ABCD已经按照左交点数的大小好位置)
A的右交点>B的左交点,所以AB可共用一个雷达;
B的右交点>C的左交点,所以BC可共用一个雷达;
C的右交点<D的左交点,所以CD不可共用一个雷达;
所以一共用2个雷达即可实现岛屿的全部覆盖。
注意,但岛屿的坐标y的绝对值大于时d,根据勾股定理可知,此时的d<r,即圆心以d为半径所画的圆与x轴是没有交点的,
即这个岛屿绝对无法被雷达覆盖,所以可以直接跳出循环,输出-1。
#include <iostream> #include <algorithm> #include <stdlib.h> #include <math.h> using namespace std; //设圆心为point struct point { double left; //左交点 double right; //右交点 }p[2010], temp; //p[2010]为圆心数组,temp为指针 //定义小于的运算。代表sort()的排序对象是各圆心与x轴的左交点。 bool operator < (point a, point b) { return a.left < b.left; } int main() { int n; double r; int kase =1; while (cin >> n >> r ) { if(n==0&&r==0) { break; } bool flag = false; //通过输入的各圆心坐标求出各自与x轴的左右交点坐标 for (int i = 0; i < n; i++) { double a, b; //x=a,y=b; cin >> a >> b; if (fabs(b) > r) //y=b>r表示此时的圆心以r为半径画的圆与x轴没有交点 { flag = true; } else { p[i].left = a * 1.0 - sqrt(r * r - b * b); //左交点 p[i].right = a * 1.0 + sqrt(r * r - b * b); //右交点 } } cout << "Case " << kase++ << ": "; if (flag) //代表有的圆与x轴没有交点,即无法实现岛屿的全部覆盖 { cout << -1 << endl; } else { int countt = 1; sort(p, p + n); //对数组p[n]里面的左右交点进行排序 temp = p[0]; //用指针temp指向第一个数组元素的地址 //对当前指针指向的圆心的右交点 与 下一个元素的左交点进行比较大小 for (int i = 1; i < n; i++) { if (p[i].left > temp.right) //如果下一个圆心的左交点>此时圆心的右交点 { countt++; //则当前的雷达数无法实现所有圆心的覆盖,需要多加1个雷达进行覆盖下一个圆心。 temp = p[i]; //此时指针指向数组的下一个元素 } else if (p[i].right < temp.right) //如果下一个圆心的左交点<此时圆心的右交点 { temp = p[i]; //则当前的雷达数可以实现所有圆心的覆盖,即可以覆盖到下一个圆心。 } } cout << countt << endl; } } }
Poj1328 用雷达覆盖所有的岛屿
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。