雷达设备(贪心算法c++实现)
【代码】雷达设备(贪心算法c++实现)
·
#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;
typedef pair<double,double> PII;
const int N = 1010;
PII q[N];
int n,d;
int main(){
scanf("%d%d",&n,&d);
bool is_failed = false;
for(int i=0;i<n;i++){
int x,y;
scanf("%d%d",&x,&y);
if(y>d) is_failed = true;
else {
double len = sqrt(d*d - y*y);
q[i] = {x+len,x-len};
}
}
if(is_failed){
puts("-1");
}else {
sort(q,q+n);
int cnt = 0;
double last = -1e9;
for(int i=0;i<n;i++){
if(last<q[i].second){
cnt++;
last = q[i].first;
}
}
printf("%d",cnt);
}
}
更多推荐
已为社区贡献20条内容
所有评论(0)