pojRadar Installation(贪心）

以每个点为圆心 d为半径画圆记录与x轴交出的区间就变成区间覆盖的问题了贪心若区间有重叠区间重叠的地方放一个雷达就可以覆盖这几个区间的点了

把该换成double 的数都换成double 这里WA了n次啊

View Code

 1 #include<stdio.h>
 2 #include<iostream>
 3 #include<algorithm>
 4 #include<cmath>
 5 using namespace std;
 6 struct node
 7 {
 8     double d1,d2;
 9 }q[10011];
10 bool cmp(node a,node b)
11 {
12     if(a.d1==b.d1)
13         return a.d2<b.d2;
14     else
15         return a.d1<b.d1;
16 }
17 int main()
18 {
19     int i,j,n,num,kk =0 ;
20     double k,d,a,b;
21     while(scanf("%d%lf",&n,&d)!=EOF)
22     {
23         if(n==0&&d==0.0)
24             break;
25         kk++;
26         int flag = 1;
27         num = 1;
28         if(d<0)
29             flag = 0;
30         for(i = 1 ;i <= n ; i++)
31         {
32             scanf("%lf%lf",&a,&b);
33             if(b<0)
34                 flag = 0;
35             if(b>d)
36                 flag = 0;
37             q[i].d1 = a*1.0-sqrt(d*d-b*b);
38             q[i].d2 = a*1.0+sqrt(d*d-b*b);
39         }
40         printf("Case %d: ",kk);
41         if(flag==0)
42         {
43             printf("-1\n");
44             continue;
45         }
46         sort(q+1,q+n+1,cmp);
47         k = q[1].d2;
48         for(i = 2 ; i <= n ; i++)
49         {
50             if(q[i].d1>k)
51             {
52                 num++;
53                 k = q[i].d2;
54             }
55             else
56             if(q[i].d2<k)
57                 k = q[i].d2;
58         }
59         printf("%d\n",num);
60     }
61     return 0;
62 }