浇水

浇水 (贪心 (star))

• 在一条长 (n) 米，宽 (m) 米的长方形草地上放置着 (k) 个喷水装置。假设长方形草地的坐标范围为([0,0]sim[n,m]) ，那么第(i)个喷水装置的位置为 ((a_i,frac{m}{2}))，也就是说喷水装置全部位于一条直线上。此外第 (i) 个喷水装置能向半径(r_i) 的圆形区域内喷水。
• 负责管理喷水装置的园丁老大爷想知道，要想覆盖整个草地，至少需要开启多少个喷水装置。

Input

• 第一行三个正整数 (k, n) 和 (m) 。其中 (m) 为偶数。
• 接下来 (k) 行，每行两个整数 (a_i) 和 (r_i)，代表第 (i) 个喷水装置的横坐标和喷水半径。

Output

• 一个整数 (ans) 代表至少需要开启的喷水装置数量。若所有装置都开启依然不能覆盖整个草地则输出 (-1)。

Sample Input1

9 16 6
0 5
2 5
4 5
6 5
8 5
10 5
12 5
14 5
16 5

Sample Output1

2

Sample Input2

8 20 2
5 3
4 1
1 2
7 2
10 2
13 3
16 2
19 4

Sample Output2

6

Hint

• 样例 (1) 解释开启位于 (4) 和 (12) 的喷水装置即可。
• (30\%) 的数据中： (k ≤ 20)；
• 另有 (20\%) 的数据中： $r_i $ 均相等；
• (100\%) 的数据中： (m ≤ 20000, r_i ≤ 10000，n, k ≤ 10^5， a_i ≤ n)。

分析

• 喷水装置在长方形的中线上，如果某个喷水装置能喷到左上角的地方，那左下角必定能喷到。
• 如果喷水装置的喷水半径小于 (frac{h}{2}) 此装置无用。
• 所以我们可以预处理出每一个喷水装置能喷到的左、右最远的距离，然后对其左边界进行排序，从左到右，一次枚举花坛的未喷到的最远点，在能喷到的装置中找到右端点最远的装置。

Code

#include <bits/stdc++.h>
const int maxn=1e5+5;
int n,N,lenth,high;
struct Node{
    double L,R;
}a[maxn];
bool cmp(const Node& a,const Node& b){
    return a.L < b.L;
}
void Read(){
    scanf("%d%d%d",&n,&lenth,&high);
    N = 0;
    for(int i = 1;i <= n;i++){
        int x,r;scanf("%d%d",&x,&r);
        if(r <= high/2)
            continue;
        a[++N].L = x - sqrt(r*r - high*high/4.0);
        a[N].R = x + sqrt(r*r - high*high/4.0);
    }
    std::sort(a+1,a+N+1,cmp);
}
void Solve(){
    double tail= 0;//记录已经浇到最右的距离
    int ans = 0,i = 1;
    while(tail < lenth){
        ans++;
        double s = tail;//记录未浇到的最右点
        for(;i<= N && a[i].L <= s;i++)
            if(tail < a[i].R)//能浇到s，就选尽量右的
            	tail=a[i].R;
        if(tail==s && s<lenth){//找不到能浇到s的点
            printf("-1
");
            return;
        }
    }
    printf("%d
",ans);
}

int main(){
    Read();
 	Solve();    
    return 0;
}