POJ 1328

题意：给你n个船的坐标x，y，还有灯塔的巡查半径，问你最少多少个灯塔可以覆盖所有船

分析：直接贪心做，找出每个船可被覆盖的灯塔的在x轴上的范围，贪心写

 1 #include <iostream>
 2 #include <cmath>
 3 #include <cstdio>
 4 #include <cstring>
 5 #include <string>
 6 #include <map>
 7 #include <iomanip>
 8 #include <algorithm>
 9 #include <queue>
10 #include <stack>
11 #include <set>
12 #include <vector>
13 //const int maxn = 1e5+5;
14 #define ll long long
15 #define MAX INT_MAX
16 #define FOR(i,a,b) for( int i = a;i <= b;++i)
17 using namespace std;
18 struct node
19 {
20     double x,y,l,r;
21 }v[1100];
22 bool cmp(node a,node b)
23 {
24     return a.l<b.l;
25 }
26 int n,d,ans,k;
27 int hhh;
28 double dl,dr;
29 int main()
30 {
31     while(scanf("%d %d",&n,&d)&&n&&d)
32     {
33         hhh=0;
34         k++;
35         memset(v,0,sizeof(v) );
36         ans=0;
37         FOR(i,1,n)
38         {
39             cin>>v[i].x>>v[i].y;
40             if(v[i].y>d)
41             {
42                  hhh=1;
43             }
44         }
45         if(hhh==1)
46         {
47             printf("Case %d: -1
", k);
48         }
49         else
50         {
51             FOR(i,1,n)
52             {
53                 v[i].l=v[i].x-sqrt(d*d-v[i].y*v[i].y);
54                 v[i].r=v[i].x+sqrt(d*d-v[i].y*v[i].y);
55             }
56 
57             sort(v+1,v+n+1,cmp);
58 
59             double dl=v[1].l,dr=v[1].r;
60             ans=1;
61 
62 
63             for(int i=2;i<=n;++i)
64             {
65                 if(v[i].l>dr)            //可以覆盖这个点
66                 {
67                    // dr=max(v[i].r,dr);
68                    dr=v[i].r;
69                    ans++;
70                 }
71                 else if(v[i].r<dr)
72                 {
73                     dr=v[i].r;
74                 }
75             }
76             printf("Case %d: %d
", k,ans);
77         }
78 
79     }
80 
81 
82     /*FOR(i,1,n)
83     {
84         cout<<v[i].l<<" "<<v[i].r<<endl;
85     }*/
86 
87 }