给定平面 xoy上 n 个开线段组成的集合 I,和一个正整数 k,试设计一个算法。
从开线段集合I中选取出开线段集合S∈I ,
使得在x轴上的任何一点 p , S 中与直线 x=p 相交的开线段个数不超过 k ,
且 ∑z∈S∣z∣ 达到最大。
这样的集合 S 称为开线段集合I 的最长 k 可重线段集的长度。
对于任何开线段z ,设其断电坐标为(x0,y0)和 (x1,y1),
则开线段 z 的长度 ∣z∣定义为: ⌊(x1−x0)2+(y1−y0)2⌋
对于给定的开线段集合 I 和正整数 k ,计算开线段集合 I 的最长 k 可重线段集的长度。
输入格式
文件的第一 行有二 个正整数 n 和 k ,分别表示开线段的 个数和开线段的可重迭数。接下来的 n 行,每行有 4个整数,表示开线段的2 个端点坐标。