wordpress做流量站,网站建设需要什么证件,自动化设备东莞网站建设,网络工程主要是干嘛的POJ-1328 题目大意#xff1a;在x轴上建立尽量少的雷达覆盖所有的岛屿。
Input#xff1a;岛屿的数量n#xff0c;雷达覆盖半径d.接下来的n行一行表示一个岛屿(x,y).
Output:每个案例的雷达最少数目. 经典的区间选点#xff01;
要搞清楚为什么排序#xff0c;然后要明…POJ-1328 题目大意在x轴上建立尽量少的雷达覆盖所有的岛屿。
Input岛屿的数量n雷达覆盖半径d.接下来的n行一行表示一个岛屿(x,y).
Output:每个案例的雷达最少数目. 经典的区间选点
要搞清楚为什么排序然后要明白如何选点。
思想排序原因小区间被满足大区间一定被满足。
(所以排序后所有岛屿都是 递增的)(即小区间都在前面。)
选点只有前一个点的右端点小于下一个点的左端点这时才选一个点即增加一个雷达因为不可能存在一个雷达可以覆盖到这两个岛屿而且此时前面用一个雷达覆盖即为最优解因为大区间包含了小区间
#includeiostream
#includealgorithm
#includemath.h
#include stdlib.h
#includevector
using namespace std;struct point{double left,right;
}p[2021],temp;bool operator (point a,point b)
{return a.leftb.left;
}
int main()
{int n;//岛屿的数量double r;//雷达半径vectorint vec;while(cinnr(n||r)){int a,b;int flag1;for(int i0;in;i){cinab;if(br){flag0;}else{p[i].left a * 1.0 - sqrt(r * r - b * b);p[i].right a * 1.0 sqrt(r * r - b * b);}}if(flag0){vec.push_back(-1);} else{int count1;//雷达的个数sort(p,pn);temp p[0];for(int i1;in;i){if(p[i].lefttemp.right){count;tempp[i];}else if(p[i].righttemp.right){tempp[i];} }vec.push_back(count);}}int kase0;int numvec.size();for(int i0;inum;i){cout Case kase : ;coutvec[i]endl;}
}
