uva12528.c

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <math.h>


typedef struct __yfunc{
    double p[9];
    double q[9];
    size_t len;
} *yfunc;

double runif(void) {
    return (double)rand()/RAND_MAX;
}

double get_value(yfunc y1, yfunc y2, double w, double d) {
    double p1, q1, p2, q2, r, r2;
    double ans1, ans2, ans = 0.0;
    int i, j;

    for (j = 0; j < w*1000; j++) {
        r = (runif() + (double)j)*0.001;
        r2 = (double)j*0.002 - r + 0.001;

        p1 = q1 = p2 = q2 = 0;
        for (i = y1->len; i >= 0; i--) {
            p1 = p1*r + y1->p[i];
            q1 = q1*r + y1->q[i];

            p2 = p2*r2 + y1->p[i];
            q2 = q2*r2 + y1->q[i];
        }
        ans1 = (p1/q1 + p2/q2)*0.5;

        p1 = q1 = p2 = q2 = 0;
        for (i = y1->len; i >= 0; i--) {
            p1 = p1*r + y2->p[i];
            q1 = q1*r + y2->q[i];

            p2 = p2*r2 + y2->p[i];
            q2 = q2*r2 + y2->q[i];
        }
        ans2 = (p1/q1 + p2/q2)*0.5;


        ans += (ans1 > d ? ans1:d) - (ans2 > d ? ans2:d);
    }

    return ans/1000.0;
}

double integral(yfunc y1, yfunc y2, double d, double w) {
    static double r, mean, err, dm;
    int i, j;
    err = mean = 0.0;
    for (i = 0; i < 10; i++) {
        r = get_value(y1, y2, w, d);
        mean += r;
        err += r*r;
    }
    mean /= 10.0;
    err = (err/10.0 - mean*mean)/9.0;

    for (i = 11; err >= 1e-10; i++) {
        r = get_value(y1, y2, w, d);
        dm = (r - mean)/i;
        err = err*(1 - (2.0/(double)i)) + dm*dm;
        mean += dm;
    }
    return mean;
}

double find(double l, double r, int w, double A, yfunc y1, yfunc y2) {
    double mid, s1;
    int i;


    while (l - r > 1e-6) {
        mid = (r + l)/2.0;
        s1 = integral(y1, y2, mid, w);
        if (A < s1)
            r = mid;
        else
            l = mid;
    }

    return r;
}

int main(void) {
    int w, d, a, k;
    struct __yfunc y1, y2;
    int i;

    srand(time(NULL));

    while (scanf("%d%d%d%d", &w, &d, &a, &k) != EOF) {
        y1.len = y2.len = k;
        for (i = 0; i <= k; i++)
            scanf("%lf", &y1.p[i]);
        for (i = 0; i <= k; i++)
            scanf("%lf", &y1.q[i]);
        for (i = 0; i <= k; i++)
            scanf("%lf", &y2.p[i]);
        for (i = 0; i <= k; i++)
            scanf("%lf", &y2.q[i]);

        printf("%.5lf\n", -find(0, -d, w, a, &y1, &y2));
    }
    return 0;
}