2535 8-22 最长k可重线段集问题
题目描述
给定平面xoy 上n 个开线段组成的集合I，和一个正整数k，试设计一个算法，从开线段集合I 中选取出开线段集合S包含于I，使得在x 轴上的任何一点p，S 中与直线x=p 相交的开线段个数不超过k，且
达到最大。这样的集合 S称为开线段集合 I的最长k可重线段集。称为最长 k可重线段集的长度。对于任何开线段z，设其端点坐标为（ x 0, y 0）和（ x1 , y1 ），则开线段z 的长度|z|定义为：
。
对于给定的开线段集合I和正整数k，计算开线段集合I的最长k可重线段集的长度。
输入格式:
输入数据的第1 行有2 个正整数n和k，分别表示开线段的个数和开线段的可重迭数。接下来的n行，每行有4个整数，表示开线段的2 个端点坐标。
输出格式:
程序运行结束时，将计算出的最长k可重线段集的长度输出
输入样例 复制
4 2 1 2 7 3 6 5 8 3 7 8 10 5 9 6 13 9
输出样例
复制
17
