我AC了之后又检查了一下代码,发现我没有写输出-1(即有小岛不能被覆盖到)的情况,却也AC了。
这里附上我一开始写的代码:
#include<bits/stdc++.h>
using namespace std;
const int N=1100;
int n,d,x[N],y[N],now=0,sum=0;
struct node{
double L;
double R;
};
bool operator <(node a,node b){
return a.R<b.R;
}
node a[N];
int main(){
scanf("%d%d",&n,&d);
for(int i=1;i<=n;++i)
{
scanf("%d%d",&x[i],&y[i]);
a[i].L=x[i]-sqrt(pow(d,2)-pow(y[i],2));
a[i].R=x[i]+sqrt(pow(d,2)-pow(y[i],2));
}
sort(a+1,a+1+n);
sum=1,now=1;
for(int i=2;i<=n;++i)
{
if(a[i].L>a[now].R)
{
++sum;
now=i;
}
}
printf("%d",sum);
return 0;
}
望改善。