比赛 20220418高一小测验 评测结果 WWWWWW
题目名称 喷水装置 最终得分 0
用户昵称 dew52 运行时间 0.062 s
代码语言 C++ 内存使用 4.01 MiB
提交时间 2022-04-18 21:33:14
显示代码纯文本
#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>

using namespace std;
const int MAXN = 1e5 + 5;
struct Node
{
    double lx;
    double ly;
    double sum;
}a[MAXN];
int T, L, W, n;
double h;
double cal (int R);
bool cmp (Node x, Node y);
int main()
{
    freopen("sprinkler.in","r",stdin);
    freopen("sprinkler.out","w",stdout);
    scanf("%d", &T);
    while (T--)
    {
        scanf("%d%d%d", &n ,&L, &W);
        h = 1.0 * W / 2;
        //cout << h << endl;
        double minn = 1000, maxx = -100;
        bool flag = false;
        int cnt = 0;
        for (int i = 1; i <= n; ++i)
        {
            int x = 0, R = 0;
            scanf("%d%d", &x, &R);
            double r = cal(R);
            //cout << x << " " << R << " ";
            //cout << cal(R) << " ";
            double lx = x - r, ly = x + r;
            //cout << lx << " " << ly << endl;
            minn = min(minn, lx);
            maxx = max(maxx, ly);
            a[i].lx = lx, a[i].ly = ly;
            a[i].sum = a[i].ly - a[i].lx;
        }
        if (minn <= 0 && maxx >= L) flag = true;
        //cout << minn << " " << maxx << endl;
        if (!flag)
        {
            puts("-1");
            return 0;
        }
        sort (a + 1, a + n + 1, cmp);
//        for (int i = 1; i <= n; ++i)
//        {
//            cout << a[i].lx << " " << a[i].ly << endl;
//        }
//        cout << endl;
        double pos_x = -10, pos_y = -10;
        for (int i = 1; i <= n; ++i)
        {
            if (pos_x <= a[i].lx && pos_y >= a[i].ly) continue;
            if (a[i].lx <= pos_x && a[i].ly >= pos_y) continue;
                pos_x = a[i].lx;
                pos_y = a[i].ly;
                cnt++;
                //cout << pos_x << " " << pos_y << endl;
                //cout << a[i].lx << " " << a[i].ly << endl; 
        }
//        for (int i = 1; i <= n; ++i)
//        {
//            pos_y = a[i].ly;
//            pos_x = a[i].lx;
//            cout << a[i].lx << " " << a[i].ly << endl;
//            cnt++;
//        }
        cout << cnt << endl;
        //puts("********************");
    }
    return 0;
}
double cal (int R)
{
    return sqrt(R * R - h * h);
}
bool cmp (Node x, Node y)
{
    if (!(abs(x.ly - y.ly) <= 1e-6))
    {
        return x.ly < y.ly;
    }
    else if (!(abs(x.lx - y.lx) <= 1e-6))
    {
        return x.lx < y.lx;
    }
}