Regional 2012 E

#include <cstdio>
#include <algorithm>

using namespace std;

#define MAXK 8
#define PARTS 250000

int W,D,A,K;
double p1[MAXK + 1],q1[MAXK + 1];
double p2[MAXK + 1],q2[MAXK + 1];
double f1[2 * PARTS + 1],f2[2 * PARTS + 1];

void precalc(int pos, double x){
    double P1 = 0,Q1 = 0,P2 = 0,Q2 = 0;

    for(int i = K;i >= 0;--i){
        P1 = P1 * x + p1[i];
        Q1 = Q1 * x + q1[i];
        P2 = P2 * x + p2[i];
        Q2 = Q2 * x + q2[i];
    }

    f1[pos] = P1 / Q1;
    f2[pos] = P2 / Q2;
}

double calc(int pos, double mi){
    return max(f1[pos],mi) - max(mi,f2[pos]);
}

int main(){
    while(scanf("%d %d %d %d",&W,&D,&A,&K) == 4){
        for(int i = 0;i <= K;++i) scanf("%lf",&p1[i]);
        for(int i = 0;i <= K;++i) scanf("%lf",&q1[i]);
        for(int i = 0;i <= K;++i) scanf("%lf",&p2[i]);
        for(int i = 0;i <= K;++i) scanf("%lf",&q2[i]);
        double dx = (double)W / 2 / PARTS;

        for(int i = 0,pos = 0;i <= 2*PARTS;++i)
            precalc(pos++,i * dx);

        double lo = 0,hi = -D,mi;

        for(int it = 0;it < 25;++it){
            mi = (lo + hi) / 2.0;

            double aux = 0;

            for(int i = 0,pos = 0;i < PARTS;++i,pos += 2)
                aux += calc(pos,mi) + 4*calc(pos + 1,mi) + calc(pos + 2,mi);

            aux *= (double)dx / 3;

            if(aux > A) hi = mi;
            else lo = mi;
        }

        printf("%.5f\n",-lo);
    }

    return 0;
}