自动搬运

查看原文

来自洛谷，原作者为

	wzm2007 这个家伙的确很懒，但还是留下了什么

搬运于2025-08-24 21:23:46，当前版本为作者最后更新于2019-03-22 22:36:02，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

因为雷达只能放在x轴上，所以每个岛屿覆盖的其实是一条线段。所以问题变为：每条线段上必须要有雷达。
1. 先把线段按照右端点从左到右排序
2. 对于最早的没有雷达的线段，把一个雷达放在它的右端点
附上代码:

#include<bits/stdc++.h>
using namespace std;
int n,d,ans;
struct node
{
    double x,y;
    bool vis=0;
}a[1010];  //存值
bool cmp(node p,node q)  //sort的比较函数
{
    return p.y<q.y;
}
int main()
{
    cin>>n>>d;
    for(register int i=0;i<n;i++)
    {
        double p,q,m;
        cin>>p>>q;
        if(q>d){cout<<-1;return 0;}
        m=sqrt(d*d-q*q);
        a[i].x=p-m,a[i].y=p+m;  //读入处理
    }
    sort(a,a+n,cmp);  //排序
    for(int i=0;i<n;i++)  //挨个循环
    {
        if(a[i].vis)continue;
        ans++;  //累加雷达数量
        a[i].vis=1;  //标记为已经被雷达扫过
        for(int j=0;j<n;j++)
            if(!a[j].vis&&a[i].y>=a[j].x)a[j].vis=1;  //标记范围内的所有点
    }
    cout<<ans;  //输出所需雷达数量
    return 0;  //完美结束
}

求通过（qwq）