#6578. 「ICPC World Finals 2019」美丽的桥梁

内存限制:1024 MiB 时间限制:10000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: PinkRabbit

题目描述

是什么将你我连结?嗯,通常是桥梁。
自古以来,人们一直在为公路,铁路和行人而建造桥梁,就如同为了运输水而修建的引水渠一般。这是人类对不便的地理环境做出的回答。

拱桥建筑(Arch Bridges Construction,简称 ABC)致力于——你猜对了,建造拱桥。这一经典的桥梁结构由从桥下的地面中延伸出的柱子支撑。相邻柱子之间的拱形结构将桥面的重量分摊到柱子上。

由 ABC 建造的桥梁通常有间隔不同间距的柱子。出于美学原因,ABC 的桥梁总是有如图所示的半圆形拱门。然而,虽然桥拱可以接触地面,但它不能延伸到地面以下。这使得一些柱子的放置方案不可能实现。

给定地形剖面图和期望的桥高 h ,通常有许多方法来建造拱桥。
我们将地面剖面模型化为由 n 个关键点 (x_1, y_1), (x_2, y_2), \ldots, (x_n, y_n) 描述的分段线性函数,其中点的 x 坐标是位置, y 坐标是该位置的海拔高度。
必须在第一个和最后一个关键点处建造第一个和最后一个柱子,而且任何其他的柱子必须建造在这些关键点上。桥梁的花费为柱子的花费(与其高度成正比)加上拱的花费(与所用材料的量成正比)。所以一座拥有 k 个高度分别为 h_1, \ldots, h_k 的柱子,且水平间距分别为 d_1, \ldots, d_{k-1} 的桥的总花费为:

\alpha \cdot \sum_{i=1}^{k}h_i + \beta \cdot \sum_{i=1}^{k-1}d_i^2

其中常数 \alpha, \beta 给定。ABC 想要知道建造每一座桥需要的最小花费。

输入格式

第一行包含四个整数 n, h, \alpha, \beta n 2 \le n \le 10^4 )为描述地形剖面图的点数, h 1 \le h \le 10^5 )表示桥期望修建的海拔高度,而 \alpha, \beta 1 \le \alpha, \beta \le 10^4 )为上面提到的花费因子。
接下来 n 行,第 i 行包含两个整数 x_i, y_i 0 \le x_1 < x_2 < \ldots < x_n \le 10^5 并且 0 \le y_i < h ),描述地形剖面图。

输出格式

输出在海拔高度 h 处从位置 x_1 建造桥梁到 x_n 的最低花费。
如果不可能建造出桥梁,输出 \texttt{impossible}

样例

样例输入 1

5 60 18 2
0 0
20 20
30 10
50 30
70 20

样例输出 1

6460

样例输入 2

4 10 1 1
0 0
1 9
9 9
10 0

样例输出 2

impossible

数据范围与提示

2 \le n \le 10^4

1 \le h \le 10^5

1 \le \alpha, \beta \le 10^4

0 \le x_1 < x_2 < \ldots < x_n \le 10^5

0 \le y_i < h

在不侵犯原题版权的情况下,本题面中文翻译基于知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议发布,注明出处时需指向本题链接。