#P4981. [2017年湖南省队集训]第二题

    ID: 4081 传统题 1000ms 128MiB 尝试: 12 已通过: 8 难度: 8 上传者: 标签>难度分类提高+/省选-排序与序列处理一维前缀和计算几何直线上包络单调栈CF2400

[2017年湖南省队集训]第二题

食堂选址

题目描述

地球上有 nn 个城市,编号为 11 至 nn,由 nn 条双向公路连成一环。第 ii 条公路长度为 did_i,连接 i−1i-1 与 ii,其中第 11 条公路连接 nn 与 11。

sl 要在一座城市建公共食堂。若选址为城市 ii,从 ii 到另一座城市 jj 的两条环上路径长度分别为 ℓ1,ℓ2\ell_1,\ell_2,送往需求量为 wjw_j 的城市 jj 的运费为 ℓ1ℓ2wj\ell_1\ell_2w_j。食堂所在城市无需运输。sl 会选择总运费最小的城市。若并列最小,他在并列城市中等概率选一座。

前 n−1n-1 座城市的需求已知。wnw_n 在实数区间 [a,b][a,b] 内均匀分布,a=ba=b 时为固定值。求每座城市被选中的概率。

输入格式

第一行三个正整数 n,a,bn,a,b,满足 n≤100000n\le100000、a≤b≤10000a\le b\le10000。

接下来 n−1n-1 行每行一个正实数,依次为 w1,…,wn−1w_1,\ldots,w_{n-1},满足 wi≤10000w_i\le10000。

最后 nn 行每行一个正实数,依次为 d1,…,dnd_1,\ldots,d_n,满足 di≤10d_i\le10。

输出格式

输出 nn 行,第 ii 行为城市 ii 被选中的概率。绝对误差不超过 0.0010.001。

样例

5 1 100
50
25
25
50
1
2
3
2
1
0.090
0.000
0.000
0.090
0.821