学习日记 2021/4/24——01

学习日记 -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;
}