P6252 [ICPC 2019 WF] Beautiful Bridges

### Warning: If you submit a malicious program, you will be banned. ### 警告：恶意提交本题将被封号。

是什么将我们连接在一起？通常是桥梁。自古以来，人们就开始建造桥梁用于道路、火车、行人以及作为运河来运输水。这是人类不屈服于不便地理条件的一种方式。 Arch Bridges Construction (ABC) 公司专门从事——你猜对了——拱桥的建造。这种经典风格的桥梁由从桥下地面延伸的柱子支撑。柱子之间的拱将桥梁的重量分布到相邻的柱子上。 ABC 建造的桥梁通常在不规则间隔处设置柱子。出于美学原因，ABC 的桥梁总是有半圆形的拱，如图 B.1 所示。然而，虽然桥拱可以接触地面，但不能延伸到地面以下。这使得某些柱子的位置不可能实现。 给定一个地面轮廓和一个期望的桥梁高度 $h$，通常有多种建造拱桥的方法。我们将地面轮廓建模为由 $n$ 个关键点 $(x_1, y_1),(x_2, y_2), \dots ,(x_n, y_n)$ 描述的分段线性函数，其中点的 $x-\text{坐标}$ 是沿桥的位置，$y-\text{坐标}$ 是沿桥该位置处的地面海拔。第一个和最后一个柱子必须建在第一个和最后一个关键点上，任何中间的柱子只能建在这些关键点上。桥梁的成本是其柱子的成本（与其高度成正比）加上其拱的成本（与使用的材料量成正比）。因此，一个有 $k$ 个高度为 $h_1, \dots , h_k$ 的柱子并且水平距离为 $d_1, \dots , 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 \leq n \leq 10^4$) 是描述地面轮廓的点的数量，$h$ ($1 \leq h \leq 10^5$) 是期望的桥梁海拔高度，$\alpha, \beta$ ($1 \leq \alpha, \beta \leq 10^4$) 是如前所述的成本因子。接下来是 $n$ 行，第 $i^{\text{th}}$ 行包含两个整数 $x_i, y_i$ ($0 \leq x_1 < x_2 < . . . < x_n \leq 10^5$ 且 $0 \leq y_i < h$)，描述地面轮廓。

输出从水平位置 $x_1$ 到 $x_n$ 在海拔高度 $h$ 处建造桥梁的最低成本。如果无法建造任何这样的桥梁，输出 `impossible`。

来源：ICPC 2019 世界总决赛。 题面翻译由 ChatGPT-4o 提供。