loj#P6227. 「网络流 24 题」最长 k 可重线段集
「网络流 24 题」最长 k 可重线段集
题目描述
给定平面 上 个开线段组成的集合 ,和一个正整数 ,试设计一个算法。
从开线段集合 中选取出开线段集合 ,
使得在x轴上的任何一点 , 中与直线 相交的开线段个数不超过 ,
且 达到最大。
这样的集合 称为开线段集合 的最长 可重线段集的长度。
对于任何开线段 ,设其端点坐标为 和 ,
则开线段 的长度 定义为: $|z| = \lfloor \sqrt{ ( x_1 - x_0 ) ^ 2 + ( y_1 - y_0 )^2 } \rfloor$
对于给定的开线段集合 和正整数 ,计算开线段集合 的最长 可重线段集的长度。
输入格式
文件的第一 行有二 个正整数 和 ,分别表示开线段的 个数和开线段的可重迭数。接下来的 行,每行有 4 个整数,表示开线段的 2 个端点坐标。
输出格式
程序运行结束时,输出计算出的最长 可重线段集的长度。
4 2
1 2 7 3
6 5 8 3
7 8 10 5
9 6 13 9
17
数据范围与提示
.