学习日记 -02
注意到,可以将喷头区分为三种喷头:
①半径小于宽度一半的喷头(简称小于,等于、大于类推);
②半径等于宽度一半的喷头;
③半径大于宽度一半的喷头;
假设计入有效的浇灌距离[s,e],说明需要在以喷头位置S为中心,半径为r的圆(覆盖范围为[S-r,S+r])中能框出出一个左端点为s,又端点为e且宽度为W的矩形。

对于小于和等于,显然无法做到,所以就不计入有用的喷头的计数;所以,每次检测到一个大于,就记录一次。
设第n个大于为, 如图,对于一个位于S,半径为r的图片说明 ,覆盖长度的一半q可以用图片说明 来计算,此时有效的覆盖范围为[S-q,S+q].
图片说明

在顺清楚覆盖范围后,就是如何选择喷头了。

这时候就可以小套一下区间覆盖问题的模板了,将覆盖范围按照左端点从小到大排序,依次处理每个范围,将已经覆盖的范围设为 (s1,e1),每次从 左端点<e1 的范围中选择 右端点最大 的一个,使它的右端点成为新的e1,直到 e1图片说明 总长度L。
同理,无解的情况就是 选择到最后一个时 e1<L.

tips:一定要注意循环内符号是否与想要的相等!!(因为打错了覆盖循环的last,de了老半天的老憨批)

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
using namespace std;
struct area { double l, r; }a[15010];

bool cmp(const area& x, const area& y)
{
    return x.l < y.l;
}

void solve(int n,int L,int W)
{
    int cnt=0,flag=1,ans=0,j=1;
    double t=0,p, r,s=0,last;

    for (int i = 1; i <= n; i++)
    {
        cin >> p >> r;
        if (r < W / 2)continue;
        cnt++;
        a[cnt].l = p - sqrt(r * r - W * W / 4);
        a[cnt].r = p + sqrt(r * r - W * W / 4);
    }

    sort(a + 1, a + cnt + 1, cmp);

    while (t < L) 
    {
        last = t;
        ans++;
        for (; a[j].l <= ***last*** && j <= cnt; j++)
            if (t < a[j].r) t = a[j].r;
        if (t == last && last < L)
            {
                cout << "-1" << endl;
                flag = 0;
                break;
            }


    }
    if (flag)cout << ans << endl;

}

int main()
{
    int T, n, L, W;
    cin >> T;
    for (int i = 1; i <= T; i++)
    {
        cin >> n >> L >> W;
        solve(n, L, W);
    }
    return 0;
}