【ACWing】112. 雷达设备

题目地址：

https://www.acwing.com/problem/content/description/114/

假设海岸是一条无限长的直线，陆地位于海岸的一侧，海洋位于另外一侧。每个小岛都位于海洋一侧的某个点上。雷达装置均位于海岸线上，且雷达的监测范围为d dd，当小岛与某雷达的距离不超过d dd时，该小岛可以被雷达覆盖。我们使用笛卡尔坐标系，定义海岸线为x xx轴，海的一侧在x xx轴上方，陆地一侧在x xx轴下方。现在给出每个小岛的具体坐标以及雷达的检测范围，请你求出能够使所有小岛都被雷达覆盖所需的最小雷达数目。

输入格式：
第一行输入两个整数n nn和d dd，分别代表小岛数目和雷达检测范围。
接下来n nn行，每行输入两个整数，分别代表小岛的x ， y x，yx，y轴坐标。同一行数据之间用空格隔开。

输出格式：
输出一个整数，代表所需的最小雷达数目，若没有解决方案则所需数目输出− 1 −1−1。

数据范围：
1 ≤ n ≤ 1000 1≤n≤10001≤n≤1000,
1 ≤ d ≤ 200 1≤d≤2001≤d≤200,
− 1000 ≤ x , y ≤ 1000 −1000≤x,y≤1000−1000≤x,y≤1000

能覆盖( x , y ) (x,y)(x,y)的雷达可以处于的下标范围是[ x − d 2 − y 2 , x + d 2 − y 2 ] [x-\sqrt {d^2-y^2},x+\sqrt {d^2-y^2}][x−d2−y2​,x+d2−y2​]（当然如果y > d y>dy>d那么雷达覆盖不到，直接输出− 1 -1−1），所以问题转化为，给定若干区间，求最少的点，使得每个区间至少包含一个点，问最少的点的数量。思路参考https://blog.csdn.net/qq_46105170/article/details/113734162。代码如下：

#include<algorithm>#include<cmath>#include<iostream>#include<vector>usingnamespacestd;usingPDD=pair<double,double>;vector<PDD>v;intn,d;intmain(){scanf("%d%d",&n,&d);v.reserve(n);intres=0;for(inti=1;i<=n;i++){doublex,y;scanf("%lf%lf",&x,&y);if(d<y){res=-1;break;}doubler=sqrt(d*d-y*y);v.emplace_back(x-r,x+r);}if(~res){sort(v.begin(),v.end(),[&](auto&a,auto&b){returna.second<b.second;});doublecur_x=-2e9;for(auto&[l,r]:v)if(cur_x<l){cur_x=r;res++;}}printf("%d\n",res);}

时间复杂度O ( n log ⁡ n ) O(n\log n)O(nlogn)，空间O ( 1 ) O(1)O(1)。