貪心
求出每個(gè)島嶼被雷達(dá)覆蓋,雷達(dá)位置的最左點(diǎn)和最右點(diǎn)
按左值排序
從左向右依次掃描
把雷達(dá)的位置放在最右點(diǎn),如果某島嶼不在范圍,就添加雷達(dá)
#include <iostream>
#include <math.h>
using namespace std;
const int MAXN=1001;
int n,d;
int sum;
double lefts[MAXN],rights[MAXN];
void qsort(int l,int r)
{
int ll=l,rr=r;
double mid=lefts[(l+r)/2];
while (ll<=rr)
{
while (lefts[ll]<mid) ll++;
while (lefts[rr]>mid) rr--;
if (ll<=rr)
{
swap(lefts[ll],lefts[rr]);
swap(rights[ll],rights[rr]);
ll++;
rr--;
}
}
if (ll<r) qsort(ll,r);
if (rr>l) qsort(l,rr);
}
void solve()
{
double std;
qsort(1,n);
sum=1;
std=rights[1];
for (int i=2;i<=n;i++)
{
if (lefts[i]>std)
{
std=rights[i];
sum++;
}
else
{
if (rights[i]<std)
{
std=rights[i];
}
}
}
}
int main()
{
int t=1;
while(1)
{
cin>>n>>d;
if (n==0&&d==0) break;
int fail=0;
for (int i=1;i<=n;i++)
{
int x,y;
cin>>x>>y;
if (y>d)
{
fail=1;
}
else
{
double l=sqrt((double)(d*d-y*y));
lefts[i]=x-l;
rights[i]=x+l;
}
}
if (fail)
{
cout<<"Case "<<t++<<": "<<-1<<endl;
}
else
{
solve();
cout<<"Case "<<t++<<": "<<sum<<endl;
}
}
return 0;
}