这是简要图示————
图中$P1,P2,P3$是小岛,绿点是雷达,紫色圆圈是雷达的作用范围。
我们需要了解一个定理(其实大家都了解):
$$\Huge{勾股定理}$$
我们假定一个方向,要从左往右查,那么要使雷达数最少,就必须让雷达尽量往右靠,也就是说,我们可以给每个小岛绑定一个雷达,小岛与雷达的距离正好是$d$。
由图,我们可以得知:
$$w= \sqrt{d^2-y^2}$$
(由此我们知道w要开double
)
算出每个雷达的坐标后,我们可以设雷达最左边为$l$,最右边为$r$,则可以按$r$排序。
排序完从头到尾一个一个试,若第$p_i$个雷达已经覆盖了$p_{i+1},p_{i+2} \cdots p_{i+k}$,
那么$i$可以直接跳转到$i+k+1$,继续执行上述操作。
边算边记,最后就可以得到答案。
AC代码:
#include<bits/stdc++.h>
using namespace std;
struct island{
int x,y;
}islands[1005];
struct rader{
float l,r;
bool operator < (const rader &p) const
{
return r<p.r;
}
}raders[1005];
int n,d;
bool v[1005];
int main()
{
while((cin>>n>>d)&&n)
{
memset(v,0,sizeof(v));
int mx=0,ans=0;
float w=0;
for(int i=1;i<=n;i++)
{
cin>>islands[i].x>>islands[i].y;
mx=max(mx,islands[i].y);
}
if(mx>d)
{
cout<<"-1"<<endl;
continue;
}
for(int i=1;i<=n;i++)
w=sqrt(d*d-islands[i].y*islands[i].y),
raders[i].l=islands[i].x-w,
raders[i].r=islands[i].x+w;
sort(raders+1,raders+n+1);
for(int i=1;i<=n;i++)
if(!v[i])
{
v[i]=1;
for(int j=1;j<=n;j++)
if(!v[j]&&raders[j].l<=raders[i].r)
v[j]=1;
ans++;
}
cout<<ans<<endl;
}
return 0;
}
代码很丑,请原谅!