P1325 雷达安装
题目：P1325 雷达安装
代码+分析：
#include<bits/stdc++.h>
using namespace std;
long long n,d,x[10005],y[10005];
struct node{
double l,r;
}a[1010];
bool cmp(node A,node B){
return A.r<B.r;
//按右端点从小到大排序
}
int main(){
cin>>n>>d;
for(int i=1;i<=n;i++){
cin>>x[i]>>y[i];
if(y[i]>d){
cout<<"-1"<<endl;
return 0;
}//判断无解情况
a[i].l=x[i]-sqrt(d*d-y[i]*y[i]);//勾股定理
a[i].r=x[i]+sqrt(d*d-y[i]*y[i]);//勾股定理
//[l,r]表示当前点的雷达所在位置
}
sort(a+1,a+n+1,cmp);
long long cnt=1,r=a[1].r;
for(int i=2;i<=n;i++){
if(a[i].l<=r) continue;//如果当前岛屿可被覆盖，就不放雷达
r=a[i].r,cnt++;//否则放置一个新的雷达
}
cout<<cnt;
return 0;
}
原文地址：https://blog.csdn.net/zzzoureiojg/article/details/143824644
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！