玩具厂
时间限制：10s 空间限制：128MB
题目描述
有N个城市，被公路依次连成了一个环，小月想在这些城市中建一个玩具厂。城市和公路都被编号为1..N，i号公路连接i-1号城市与i号城市（1号公路连接N号城市与1号城市），每个城市对玩具的需求为wi，每条公路的长度为di。当我们在第i号城市建玩具厂时，我们需要将玩具运输到其他城市（当然i城市除外）。设第i号城市到第j号城市的两条路径长度分别为l1、l2，则将玩具运输到第j号城市的费用为l1*l2*wj。总的运输费用为将玩具运到所有城市的运输费用的总和。
小月当然想要总的运输费用最少，所以他会选最优的城市建玩具厂，如果有多个最优的城市，小月会等概率的选取其中一个建玩具厂。
由于小月的调查工作没做好，我们只知道1..N-1号城市的wi，而N号城市的wi我们只知道它的取值范围[a,b]，我们假设wi的值在实数区间[a,b]上的概率是均匀分布的。
没办法，现在小月只好去进行第二次调查，于是我们想知道每个城市建玩具厂的概率是多少。
输入格式
第一行有三个正整数N，a，b。
接下来N-1行每行一个正实数，为w[1]到w[N-1]。
接下来N行每行一个正实数，为d[1]到d[N]。
输出格式
一共有N行，每行一个实数，表示1到N号城市建玩具厂的概率，保留3位小数。
样例输入
5 1 100 50 25 25 50 1 2 3 2 1
样例输出
0.090 0.000 0.000 0.090 0.821
提示
【样例说明】
当w[5]<18.75时，将在1或4号城市建玩具厂，当w[5]>18.75时，将在5号城市建玩具厂，当w[5]=18.75时，将在1或4或5建玩具厂。
【数据规模和约定】
30%的数据中：N<=1000。
30%的数据中：a=b。
100%的数据中：N<=100000,a<=b<=10000,w[i]<=10000,d[i]<=10。
题目来源
没有写明来源