

$22.$最长k可重线段集问题

题目

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

题解

其实和$21$题差不多。