#P17741. [ICPC 2019 Xuzhou R] K-rectangle
[ICPC 2019 Xuzhou R] K-rectangle
题目描述
平面上有 个点,坐标分别为 ,满足 且 。
你需要放置若干个矩形来覆盖所有这些点,并遵循以下约束条件。(若一个点位于矩形内部或矩形边上,则称该点被覆盖)
- 矩形的底边必须落在 轴上。
- 一个矩形的代价为 ,其中 由输入给定。
- 任意两个不同的矩形不能有交集。
- 矩形可以退化为两条线,即 。
请计算覆盖所有点的最小总代价。
输入格式
第一行包含两个整数 和 (,)—— 点的个数与题目中描述的系数。
接下来的 行,每行包含两个整数 和 (,)—— 表示第 个点位于 。
输出格式
输出覆盖所有点的最小总代价。
1 2
-666 666
1332
2 66666
-666 666
666 666
45286668
提示
翻译由 DeepSeek V4 Pro 完成