ZOJ Monthly, October 2015 K题
二分答案+验证
#include#include #include #include #include using namespace std;const double pi=3.1415926535898;const int maxn=100000+10;struct cuboids{ double z; double width,length,height;}c[maxn];struct sphere{ double r; double z;}s[maxn];double W,L,V;int T,m,n;double Min,Max,Mid;double qiu(double r1,double h){ return pi/6*h*(3*(r1*r1+r1*r1-h*h)+h*h);}int main(){ scanf("%d",&T); while(T--) { scanf("%lf%lf%lf",&W,&L,&V); scanf("%d%d",&m,&n); double vNow=0; for(int i=1;i<=m;i++) scanf("%lf%lf%lf%lf",&c[i].z,&c[i].width,&c[i].length,&c[i].height); for(int i=1;i<=n;i++) scanf("%lf%lf",&s[i].z,&s[i].r); Min=0; Max=V; for(int i=1;i<=m;i++) Max=Max+c[i].width*c[i].length*c[i].height; for(int i=1;i<=n;i++) Max=Max+4.0/3.0*pi*s[i].r*s[i].r*s[i].r; Max=Max/(W*L); Mid=(Min+Max)/2.0; int t=500; while(t--) { vNow=W*L*Mid; for(int i=1;i<=m;i++) { if(c[i].z-c[i].height/2>=Mid) continue; else if(c[i].z+c[i].height/2<=Mid) vNow=vNow-c[i].width*c[i].length*c[i].height; else vNow=vNow-c[i].width*c[i].length*(Mid-(c[i].z-c[i].height/2)); } for(int i=1;i<=n;i++) { if(Mid<=s[i].z-s[i].r) continue; else if(Mid>=s[i].z+s[i].r) vNow=vNow-4.0/3.0*pi*s[i].r*s[i].r*s[i].r; else if(Mid>s[i].z-s[i].r&&Mid<=s[i].z) { vNow-=pi*s[i].r*s[i].r*s[i].r*4/3/2; vNow+=qiu(s[i].r,s[i].z-Mid); } else { vNow-=pi*s[i].r*s[i].r*s[i].r*4/3/2; vNow-=qiu(s[i].r,Mid-s[i].z); } } if(Max-Mid<1e-8) break; if(vNow>V) { Max=Mid; Mid=(Min+Max)/2.0; } else { Min=Mid; Mid=(Min+Max)/2.0; } } printf("%.6lf\n",Mid); } return 0;}