比赛 |
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;
}
}