33OJ
登录 注册

#P17741. [ICPC 2019 Xuzhou R] K-rectangle

[ICPC 2019 Xuzhou R] K-rectangle

题目描述

平面上有 nn 个点,坐标分别为 (x1,y1),(x2,y2),…,(xn,yn)(x_1, y_1), (x_2, y_2), \dots, (x_n, y_n),满足 xi<xi+1x_i < x_{i+1} 且 yi>0y_i > 0。

你需要放置若干个矩形来覆盖所有这些点,并遵循以下约束条件。(若一个点位于矩形内部或矩形边上,则称该点被覆盖)

  1. 矩形的底边必须落在 xx 轴上。
  2. 一个矩形的代价为 高度×(宽度+k)\text{高度} \times (\text{宽度} + k),其中 kk 由输入给定。
  3. 任意两个不同的矩形不能有交集。
  4. 矩形可以退化为两条线,即 宽度=0\text{宽度} = 0。

请计算覆盖所有点的最小总代价。

输入格式

第一行包含两个整数 nn 和 kk(1≤n≤4×1051 \le n \le 4\times10^5,1≤k≤1061\le k \le 10^6)—— 点的个数与题目中描述的系数。

接下来的 nn 行,每行包含两个整数 xix_i 和 yiy_i(−106≤xi≤106-10^6 \le x_i \le 10^6,1≤yi≤1061\le y_i \le 10^6)—— 表示第 ii 个点位于 (xi,yi)(x_i, y_i)。

输出格式

输出覆盖所有点的最小总代价。

1 2
-666 666
1332
2 66666
-666 666
666 666
45286668

提示

翻译由 DeepSeek V4 Pro 完成