Information
- ID
- 3
- Time
- 1000ms
- Memory
- 512MiB
- Difficulty
- 7
- Tags
- # Submissions
- 122
- Accepted
- 29
- Uploaded By
跟浮点数有关的题都简单不到哪去。
难度: 绿
算法标签: 贪心
这道题没什么难度,主要是调代码。具体解析可以看一本通或洛谷题解。
注意: 不能覆盖宽度的水龙头要无视掉。我因此调了 3 个小时。
#include<bits/stdc++.h>
using namespace std;
int tc,n,m,w,x,y,ans,bj,j;
double k=1e-12,p,s,t;
struct st{
double l,r;
}d[20000];
bool cmp(st a,st b){
if(a.l!=b.l) return a.l<b.l;
return a.r<b.r;
}
int main(){
scanf("%d",&tc);
while(tc--){
ans=0,bj=1,t=0,j=1;
scanf("%d%d%d",&n,&m,&w);
for(int i=1;i<=n;i++){
scanf("%d%d",&x,&y);
if(y<=w/2){
i--;
n--;
continue;
}
d[i].l=max(0.0,double(x)-sqrt(y*y*1.0-(w/2.0)*(w/2.0)));
d[i].r=min(m*1.0,double(x)+sqrt(y*y*1.0-(w/2.0)*(w/2.0)));
}
sort(d+1,d+n+1,cmp);
while(t<m){
ans++;
s=t;
for(;d[j].l<=s&&j<=n;j++) t=max(t,d[j].r);
if(s==t&&s<m){
printf("-1\n");
bj=0;
break;
}
}
if(bj) printf("%d\n",ans);
}
return 0;
}
By signing up a HFOJ universal account, you can submit code and join discussions in all online judging services provided by us.