Chieh's Blog

Because Of Coding

ZOJ Problem Set - 3913 Bob wants to pour water

Chieh posted @ 2015年11月01日 15:08 in NO Answer No Speak , 235 阅读
#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;
}

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter