【题目链接】

ybt 1424：【例题3】喷水装置

【题目考点】

1. 贪心算法：区间覆盖

【解题思路】

每个喷头覆盖的区域是一个圆形，草坪上被一个喷头覆盖的有效区域是一个矩形，该矩形的左端点坐标到右端点坐标形成一个线段。只有半径$r>w/2$的喷头可以完整覆盖一段草坪。
设p位置的喷头半径为r，圆心为P半径为r的圆与草坪上边界线段相交于点A和点C。弦AC的中点为B。那么一定有PB垂直于AC，已知$PB=w/2$。由勾股定理可知：$AB=BC=\sqrt{P{C}^2-P{B}^2}=\sqrt{r^2-(w/2{)}^2}=\sqrt{r^2-w^2/4}$
因此A点位置为$p-\sqrt{r^2-w^2/4}$，C点位置为$p+\sqrt{r^2-w^2/4}$。
每个喷头覆盖草坪的范围可以视作实数域上的一个区间，范围是$[p-\sqrt{r^2-w^2/4},p+\sqrt{r^2-w^2/4}]$。
该题问最少使用多少喷头可以覆盖草坪，即询问在给定多个区间中最少选择多少区间可以覆盖给定的线段。该问题为实数域上的区间覆盖问题。

贪心求区间覆盖问题

关注点：上一次选择的区间的右端点，初值为0。
贪心选择：在所有包含关注点的区间中，选择右端点最大的区间。
贪心选择性质的证明：

1. 证明：最优解包含第一次的贪心选择：在所有包含0的区间中，选择右端点最大的区间

证明：
第0位置总该被包含到某个区间中。如果选择的区间不包括0，那么无法完成区间覆盖。
这一次选择的，也就是唯一包含第0位置的区间，记该区间为$a_g$。
反证法： 假设存在一组最优解不包含贪心选择：$a_1,a_2,...,a_n$是选择的区间，$a_1$~$a_n$按左端点从小到大排序，其中没有$a_g$。
其中区间$a_1$中一定包含第0位置，否则如果$a_1$的左端点大于0，后面的区间左端点都大于$a_1$的左端点，第0位置就不会被任何区间包含，这就不是一组解了。
用$a_g$替换$a_1$，得到$a_g,a_2,...,a_n$，$a_1$和$a_g$都包括第0位置，而$a_g$的右端点大于$a_1$的右端点，替换后一定可以覆盖整个区间。
因此$a_g,a_2,...,a_n$也是该问题的一组最优解。得到了包含贪心选择的最优解，假设不成立，原命题得证。

2. 证明：在最优解包含前k次的贪心选择的情况下，存在最优解包含第k+1次的贪心选择。

证明方法同上。把“第0位置”变为“第k次贪心选择的右端点”即可。

具体做法：

1. 只关注半径大于$w/2$的喷头覆盖的范围将其转换为区间，保存在数组中。
2. 对所有区间按左端点升序排序。将关注点初值设为0.
3. 如果当前区间左端点大于关注点，则存在无法被覆盖的区域，区间覆盖失败。
4. 枚举所有左端点小于等于关注点的区间，求出这些区间右端点的最大值。
5. 选择右端点最大的区间，进行计数。记录关注点为当前区间的右端点。
6. 遍历所有区间后如果最后一个区间的右端点小于待覆盖区间的右端点，则区间覆盖失败。
7. 如果区间覆盖成功，输出选择区间的数量。

【题解代码】

解法1：贪心算法

#include<bits/stdc++.h>
using namespace std;
#define N 15005
struct Interval//区间类
{
	double l, r;//表示区间[l,r]
};
bool cmp(Interval a, Interval b)
{//按左端点升序排序 
	return a.l < b.l;	
}
int main()
{
	int t, n, an, i, ct;
	double l, w, p, r, lastR, tr; 
	bool isOk;
	Interval a[N];
	cin >> t;
	while(t--)
	{
		an = 0;//an：a数组元素个数。a数组下标从1到an。 
		cin >> n >> l >> w;
		for(int i = 1; i <= n; ++i)
		{
			cin >> p >> r;
			if(r >= w/2)//如果半径小于宽一半，对该问题无意义，不加入。 
			{
				a[++an].l = p-sqrt(r*r-w*w/4);
				a[an].r = p+sqrt(r*r-w*w/4);
			}
		}
		sort(a+1, a+1+an, cmp);//按照左端点从小到大排序 共有an个元素 
		i = 1, ct = 0, lastR = 0, tr = 0, isOk = true;//lastR：关注点。已经被覆盖区间的右端点
		while(i <= an && lastR < l)
		{
			if(a[i].l > lastR)
			{//如果当前区间左端点大于上一个选择的区间的右端点，则存在一段线段无法被覆盖 
				isOk = false;
				break;
			}
			while(i <= an && a[i].l <= lastR)
			{//在所有左端点小于等于关注点的区间中，选择右端点最大的区间 
				tr = max(tr, a[i].r);//tr：临时的区间右端点的最大值。tr的初值为lastR，当前区间右端点的最大值一定大于等于lastR才有意义。 
				i++;
			}
			lastR = tr;
			ct++;//选择区间的数量 
		}
		cout << (isOk ? ct : -1) << endl;//isOk：是否完成区间覆盖，如果完成输出区间数ct，如果未完成输出-1 
	}
	return 0;
}