y总题解: https://www.acwing.com/solution/content/1061/
左端点排序操作细节: https://www.acwing.com/solution/content/10615/
画图清晰的: https://www.acwing.com/solution/content/123740/
算法1:贪心-区间选点-排序(结构体存储) $O(nlogN)$
//转换:雷达放那可以覆盖当前小岛,转换到某一个区间;
//问题抽象:给定若干区间,最少选择多少个点,使得每个区间上至少有一个点;
//知识应用:同模板905题,区间选点
//贪心策略:
//1. 将所有区间按右端点排序;时间瓶颈在排序,NlogN,数据范围可以到10万级别
// 按左端点排序也可以,倒着扫描或者维护出右端点的最小值
//2. 依次扫描每个线段,
// 情况1,上次选择的点不在当前区间,则选择当前区间右端点,更有可能覆盖后面的;
// 情况2,上次选择的点在区间内,则当前区间已经被覆盖,直接看下一个区间
#include <bits/stdc++.h>
using namespace std;
const int N = 1010;
struct node{
double l, r;
bool operator< (const node& t) const{
return r < t.r; //按照右端点排序
}
}a[N];
int n, d, res;
int main() {
cin >> n >> d;
for (int i = 0, x, y; i < n; ++ i) {
cin >> x >> y;
if (y > d) { //y坐标大于了雷达半径 无法覆盖
cout << -1;
return 0;
}
double len = sqrt(d*d - y*y);
a[i] = {x - len, x + len};
}
sort(a, a+n);
double last = -2e9;
for (int i = 0; i < n; ++ i)
if (a[i].l > last) {
last = a[i].r;
res++;
}
cout << res;
return 0;
}
算法2:贪心-区间选点-排序(pair存储) $O(nlogN)$
#include <bits/stdc++.h>
using namespace std;
typedef pair<double, double> PDD;
const int N = 1010;
PDD a[N];
int n, d;
int main() {
cin >> n >> d;
for (int i = 0, x, y; i < n; ++ i) {
cin >> x >> y;
if (y > d) {
cout << -1;
return 0;
}
double len = sqrt(d*d - y*y); //勾股定理计算出长度
a[i] = {x+len, x-len}; //按照右端点排序,所有右端点放在first位置
}
sort(a, a+n);
int cnt = 0;
double last = -2e9;
for (int i = 0; i < n; ++ i)
if (a[i].second > last) {
cnt ++;
last = a[i].first;
}
cout << cnt;
return 0;
}