广州门户网站,上海网站建设公司有多少家,wordpress 中文版本,黑帽seo论坛题目链接#xff1a;http://acm.hust.edu.cn/vjudge/problem/visitOriginUrl.action?id27586 题意#xff1a; 在海岸线上摆放雷达并限定雷达覆盖半径d#xff0c;再以海岸线为轴#xff0c;给定海上岛屿坐标#xff0c;求至少需要多少雷达可以覆盖所以岛屿#xff0c;如…题目链接http://acm.hust.edu.cn/vjudge/problem/visitOriginUrl.action?id27586 题意 在海岸线上摆放雷达并限定雷达覆盖半径d再以海岸线为轴给定海上岛屿坐标求至少需要多少雷达可以覆盖所以岛屿如果不能输出-1。 案例 Sample Input 3 2 1 2 -3 1 2 1 1 2 0 2 0 0 Sample Output Case 1: 2Case 2: 1 分析 可以转换为区间覆盖问题。以岛屿为圆心雷达扫射半径为半径求出此圆与x轴即海岸线交点坐标两交点坐标间即为雷达摆放区间包括两交点在此区间任意位置摆放雷达均可覆盖岛屿。接下来即为区间覆盖求解问题了。 源代码 1 #includecstdio2 #includecmath3 #includealgorithm4 using namespace std;5 int n,num;6 struct former7 {8 double l;9 double r;
10 }a[1005];
11 double cmp(former m,former t)//区间排序
12 {
13 if(m.rt.r) return m.lt.l;
14 else
15 return m.rt.r;
16 }
17 void change()//计算所需雷达
18 {
19 int k0;
20 sort(a,an,cmp);
21 for(int j1;jn;j)
22 {
23 if(a[j].la[k].r)
24 {
25 num;
26 kj;
27 }
28 }
29 }
30 int main()
31 {
32 int cnt0;
33 double x,y,d;
34 while(scanf(%d%lf,n,d)nd)
35 {
36 num1;
37 for(int i0;in;i)
38 {
39 scanf(%lf%lf,x,y);
40 if(dy||d0)//判断是否有岛屿超出雷达覆盖范围
41 num-1;
42 a[i].lx-sqrt(d*d-y*y);//岛屿转换可摆放雷达区间
43 a[i].rxsqrt(d*d-y*y);
44 }
45 if(num-1)
46 printf(Case %d: -1\n,cnt);
47 else
48 {
49 change();
50 printf(Case %d: %d\n,cnt,num);
51 }
52 }
53 return 0;
54 } 转载于:https://www.cnblogs.com/huaszjh/p/4719074.html
