P3737 [HAOI2014]遥感监测 题解

· · 题解

P0 前言：

本题解有画图解析，作者美术不行，勿喷。

P1 题意：

给你 n 个在海上的激光点，你可以在陆地上建若干个放射电望远镜用来照射激光点，每个放射电望远镜的放射范围为一个以自己为圆心半径为 r 的圆，请问最少需要多少个放射电望远镜。

P2 思路：

贪心的想一想我们可以发现两点：
一、建放射电望远镜的地方一定是陆地与海的分界线，否则肯定可以在往海边挪一挪使其更接近激光点。
二、因为题目中没有提到无解的情况，所以放置 n 个放射电望远镜一定可以照射到每一个激光点。

仔细看看题意，我们又可以发现，这道题十分像区间贪心，给你许多的区间让你求出最少需要多少个区间可以覆盖到所有点，只不过我们现在这个区间是平面的，不是线性的。

那能不能把它转化成平面的呢？
答案是可以。

我们来画图理解一下。 画完图你发现了吗，其实 PQ 这条线段就是区间，PQ 的长度就是区间的长度，这样就把平面的区间转化成了线性的区间。
而 PQ 怎么求呢？ 我们可以加几条辅助线，那么根据勾股定理，P 在 x 轴上的位置就变成了 x-\sqrt{r^2-y^2}，Q 在 x 轴上的位置同理为 x+\sqrt{r^2-y^2}，长度便是 2\sqrt{r^2-y^2}。

P3 代码：

求出了所有的区间，便该贪心了，区间贪心不会的自己去搜，网上有很多区间贪心详解，各种区间贪心都有，这里只给代码了。

#include <bits/stdc++.h>
using namespace std;
int n , r , x , y , ans;
struct node{
    double l , r;
}a[1005];
double end_;
//a[i].l,a[i].r,end_都是double类型因为用到了勾股定理
//ans就是答案，最少需要用到的区间
bool cmp(node a , node b){
    return a.r < b.r;
}//按照左端点从小到大排序
int main(){
    cin >> n >> r;
    for(int i = 1; i <= n; i++){
        cin >> x >> y;
        double dis = sqrt(r * r - y * y);
        a[i].l = x - dis;
        a[i].r = x + dis;
        //算出上述PQ的距离
    }
    sort(a + 1 , a + 1 + n , cmp);
    ans++;
    end_ = a[1].r;
    for(int i = 2; i <= n; i++){
        if(a[i].l > end_){
            ans++;
            end_ = a[i].r;
            if(a[i].r == a[i + 1].l) i++;
        }
    }//区间贪心
    cout << ans;
    return 0;
}