好贷网好贷款

UVa:10382 Watering Grass

发布时间:2016-12-5 2:25:20 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"UVa:10382 Watering Grass",主要涉及到UVa:10382 Watering Grass方面的内容,对于UVa:10382 Watering Grass感兴趣的同学可以参考一下。

贪心。 先根据坐标排序。 除了两头的圆,每个圆都与矩形有左右两边的交点。 第一个圆要求半径大于圆心到矩形左上角的距离,右交点最靠右的情况。 之后选取满足 半径 大于 之前圆与矩形的右交点 的前提下,右交点最靠右的情况。 最后一个圆要求右交点大于等于矩形长度。       #include<iostream> #include<cstdio> #include<cmath> #include<algorithm> #define EPS 1e-6 using namespace std; int cmpDouble(double a, double b) { if(fabs(a - b) < EPS) return 0; // a == b else if(a - b > 0) return 1; // a > b else return -1; // a < b } struct Water { double p,r; }; bool cmp(Water a,Water b) { if(a.p==b.p) return a.r<b.r; return a.p<b.p; } int main() { int n; double l,w; while(scanf("%d%lf%lf",&n,&l,&w)!=EOF) { Water a[10005]; for(int i=0; i<n; ++i) scanf("%lf%lf",&a[i].p,&a[i].r); sort(a,a+n,cmp); int ans=0; double st=0; int key=-1; bool q=false; for(int i=0; i<n; ++i) { if(i<=key) continue; double mx=-1; for(int j=i; j<n; ++j) { double l=sqrt((a[j].p-st)*(a[j].p-st)+(w/2)*(w/2)); if(cmpDouble(a[j].r,l)>=0) { double t=a[j].p+sqrt(a[j].r*a[j].r-w/2*w/2); if(cmpDouble(t,mx)==1) { mx=t; key=j; } } } if(cmpDouble(-1,mx)==0) break; else ans++; st=mx; if(cmpDouble(st,l)==1) break; } if(cmpDouble(st,l)==-1) q=true; if(q==true) printf("-1\n"); else printf("%d\n",ans); } return 0; }  

上一篇:sql时间格式化
下一篇:代码检查错误列表总结

相关文章

相关评论