← 返回题目
题库练习 最长k可重线段集问题
← 上一题 下一题 →

A2406 | 最长k可重线段集问题

时间限制1s
内存限制128MB
通过 / 提交0/0

题目描述

给定平面 $x-O-y$ 上 $n$ 个开线段组成的集合 $I$，和一个正整数 $k$ 。试设计一个算法，从开线段集合 $I$ 中选取出开线段集合 $S\subseteq I$ ,使得在 $x$ 轴上的任何一点 $p$，$S$ 中与直线 $x=p$ 相交的开线段个数不超过 $k$，且$\sum\limits_{z\in S}|z|$达到最大。这样的集合 $S$ 称为开线段集合 $I$ 的最长 $k$ 可重线段集。$\sum\limits_{z\in S}|z|$ 称为最长 $k$ 可重线段集的长度。

对于任何开线段 $z$，设其断点坐标为 $(x_0,y_0)$ 和 $(x_1,y_1)$，则开线段 $z$ 的长度 $|z|$ 定义为：
$$|z|=\lfloor\sqrt{(x_1-x_0)^2+(y_1-y_0)^2}\rfloor$$

对于给定的开线段集合 $I$ 和正整数 $k$，计算开线段集合 $I$ 的最长 $k$ 可重线段集的长度。

输入格式

文件的第一 行有 $2$ 个正整数 $n$ 和 $k$，分别表示开线段的个数和开线段的可重叠数。

接下来的 $n$ 行，每行有 $4$ 个整数，表示开线段的 $2$ 个端点坐标。

输出格式

程序运行结束时，输出计算出的最长 $k$ 可重线段集的长度。

输入输出样例

输入 #1
4 2
1 2 7 3
6 5 8 3
7 8 10 5
9 6 13 9
输出 #1
17
C++ 编辑器
输入
输出