Latinamerica Regional 2012 E

lat2012E.cpp

#include <iostream>
#include <cstdio>
#include <cmath>

using namespace std;

int W, D, A, K;
int p1[10], q1[10], p2[10], q2[10];

inline double y1(double x) {
    double ans = 0, t = 0;
    for(int i=K; i>=0; i--) {
        ans = ans*x + p1[i];
        t = t*x + q1[i];
    }
    return ans/t;
}
inline double y2(double x) {
    double ans = 0, t = 0;
    for(int i=K; i>=0; i--) {
        ans = ans*x + p2[i];
        t = t*x + q2[i];
    }
    return ans/t;
}
inline double y(double x, double d) {
    double t1 = y1(x);
    if(t1<d)
        return 0;
    double t2 = y2(x);
    //cout<<"@ "<<t1<<" "<<t2<<endl;
    return t1-max(t2, d);
}

const double dx = 1e-4, eps = 1e-9;

inline double integrate(double d) {
    double ans=0, t1, t2, t3;
    t3 = y(0, d);
    for(double i=0; i+dx<W+eps; i+= dx) {
        t1 = t3;
        t2 = y(i+dx/2, d);
        t3 = y(i+dx, d);
        ans += (t1+4*t2+t3)*dx/6;
    }
    return ans;
}

int main() {
    while(cin>>W>>D>>A>>K) {
        for(int i=0; i<=K; i++)
            scanf("%d", &p1[i]);
        for(int i=0; i<=K; i++)
            scanf("%d", &q1[i]);
        for(int i=0; i<=K; i++)
            scanf("%d", &p2[i]);
        for(int i=0; i<=K; i++)
            scanf("%d", &q2[i]);
        double lo = 0, hi = D, mid, t;
        while(hi-lo>2e-6) {
            mid = (lo+hi)/2;
            t = integrate(-mid);
            if(t<A)
                lo = mid;
            else
                hi = mid;
        }
        mid = (lo+hi)/2;
        //cout<<integrate(-mid)<<endl;
        printf("%.5f\n", mid);
    }
}