雷达设备【问题转化+区间贪心】

根据题意，可以知道也就是有k个区间，要求每个区间至少包含一个点，也就是把陆地这个点转化成区间，如图所示，只要雷达在这交线上结果就成立，也就是可以覆盖到陆地。所以问题就转化求k个区间每个区间至少包含一个点，求最少需要多少个点。

算法步骤：

1.通过勾股定理算出区间范围，len = sqrt(R*R – y*y), 左端点x – len, 右端点x + len.

2.然后将区间按右端点从小到大排序

3.判断上一个画点的区级现在这个区间是否右交集，如果没有那么添加新的点。

证明：

首先上述做法一定可以保证所有区间都至少包含一个点。

然后我们再证明这样选出的点的数量是最少的，不妨设选出的点数是 m：

按照上述做法，我们选择的点都是某个区间的右端点，而且由于区间按右端点排好序了，所以我们选择的点也是排好序的；
只有在当前区间和上一个点所对应的区间是没有交集时，我们才会选择一个新点，所以所有选出的点所对应的区间是如下图所示的情况，两两之间没有交集。

format,png
所以我们找到了 m 个两两之间没有交集的区间，因此我们至少需要选 m 个点。而且通过上述做法，我们可以只选 m 个点。因此最优解就是 m。

附上代码：

  1 #include <iostream>
  2 #include <algorithm>
  3 #include <cstring>
  4 #include <cmath>
  5 using namespace std;
  6 typedef pair<double, double> PDD;
  7 const int N = 1e3 + 5;
  8 const double eps = 1e-6;
  9 PDD segs[N];
 10 int main(){
 11     bool is_successful = true;
 12     int n, r;
 13     cin >> n >> r;
 14     for(int i = 0, x, y; i < n; ++ i){
 15         cin >> x >> y;
 16         if(y > r){
 17             is_successful = false;
 18             break;
 19         }
 20         double len = sqrt(r*r - y*y);//根据勾股定理，把要求的问题转化成区间问题
 21         segs[i] = make_pair(x + len, x - len);
 22     }
 23     if(!is_successful) puts("-1");
 24     else{
 25         double last = -999999;
 26         int res = 0;
 27         sort(segs, segs+n);
 28         for(int i = 0; i < n; ++ i){
 29             if(last + eps < segs[i].second){//与上一个点所在的区间没有交集
 30                 res++;
 31                 last = segs[i].first;
 32             }
 33         }
 34         cout << res << endl;
 35     }
 36     return 0;
 37 }