ZOJ Problem Set - 3913 Bob wants to pour water
Chieh
posted @ 2015年11月01日 15:08
in NO Answer No Speak
, 248 阅读
#include <iostream> #include <cstdio> #include <cstring> #include <cmath> #include <algorithm> #include <vector> #include <map> #include <stack> #include <queue> #include <set> #define LL long long #define INF 1e9 #define EPS 1e-9 using namespace std; const double PI=3.1415926535898; double CalSphere(double r,double h) { return PI*(r*h*h-1.0*h*h*h/3); } const int maxn=123456; struct he { double ch,w,l,h,r; } Sky[maxn*2]; double w,l,v; int n,m; double maxH; void init() { maxH=0; scanf("%lf%lf%lf%d%d",&w,&l,&v,&n,&m); for(int i=1; i<=n; i++) { scanf("%lf%lf%lf%lf",&Sky[i].ch,&Sky[i].w,&Sky[i].l,&Sky[i].h); Sky[i].ch=Sky[i].ch-Sky[i].h/2; maxH=max(maxH,Sky[i].ch+Sky[i].h); } for(int i=1; i<=m; i++) { scanf("%lf%lf",&Sky[n+i].ch,&Sky[n+i].r); Sky[n+i].ch=Sky[n+i].ch-Sky[n+i].r; maxH=max(maxH,Sky[n+i].ch+Sky[n+i].r*2); } } bool check(double h) { double nv=0; for(int i=1; i<=n; i++) { double mh=Sky[i].ch+Sky[i].h; if(mh<=h) { nv+=Sky[i].h*Sky[i].l*Sky[i].w; } else if(Sky[i].ch>=h) { } else { double hh=h-Sky[i].ch; nv+=hh*Sky[i].l*Sky[i].w; } } for(int i=1; i<=m; i++) { double mh=Sky[n+i].ch+Sky[n+i].r*2; if(mh<=h) { nv+=CalSphere(Sky[n+i].r,Sky[n+i].r*2); } else if(Sky[n+i].ch>=h) { } else { double hh=h-Sky[n+i].ch; nv+=CalSphere(Sky[n+i].r,hh); } } double cm=w*l*h; if(cm<=nv+v) { return 1; } else { return 0; } } double BRSearch() { double l=0; double r=maxH+1000; double ans=0; while(l<=r) { double mid=(l+r)/2; bool ck=check(mid); if(ck) { ans=mid; l=mid+EPS; } else { r=mid-EPS; } } return ans; } void play() { double ans=BRSearch(); if(ans>maxH) { for(int i=1; i<=n; i++) { v+=Sky[i].w*Sky[i].l*Sky[i].h; } for(int i=1; i<=m; i++) { v+=CalSphere(Sky[n+i].r,Sky[n+i].r*2); } ans=v/(w*l); printf("%.8f\n",ans); } else { printf("%.8f\n",ans); } } int T; int main() { scanf("%d",&T); while(T--) { init(); play(); } return 0; }