Problem1203--#6227. 「网络流 24 题」最长k可重线段集问题

1203: #6227. 「网络流 24 题」最长k可重线段集问题

Time Limit: 1 Sec  Memory Limit: 256 MB
Submit: 0  Solved: 0
[Submit] [Status] [Web Board] [Creator:]

Description

给定平面 xoy\text{xoy}xoynnn 个开线段组成的集合 I\text{I}I,和一个正整数 kkk,试设计一个算法。

从开线段集合I\text{I}I中选取出开线段集合S∈I\text{S}\in \text{I}SI ,

使得在x轴上的任何一点 p\text{p}pS\text{S}S 中与直线 x=p\text{x}=\text{p}x=p 相交的开线段个数不超过 k\text{k}k

∑z∈S∣z∣\sum_{\text{z} \in \text{S}}|z|zSz 达到最大。

这样的集合 S\text{S}S 称为开线段集合I\text{I}I 的最长 k\text{k}k 可重线段集的长度。

对于任何开线段z\text{z}z ,设其断电坐标为(x0,y0)( x_0 , y_0 )(x0,y0)(x1,y1)( x_1 , y_1 )(x1,y1)

则开线段 z\text{z}z 的长度 ∣z∣|\text{z}|z定义为: ∣z∣=⌊(x1−x0)2+(y1−y0)2⌋|z| = \lfloor \sqrt{ ( x_1 - x_0 ) ^ 2 + ( y_1 - y_0 )^2 } \rfloorz=(x1x0)2+(y1y0)2

对于给定的开线段集合 I\text{I}I 和正整数 k\text{k}k ,计算开线段集合 I\text{I}I 的最长 k\text{k}k 可重线段集的长度。

输入格式

文件的第一 行有二 个正整数 n\text{n}nk\text{k}k ,分别表示开线段的 个数和开线段的可重迭数。接下来的 n\text{n}n 行,每行有 4个整数,表示开线段的2 个端点坐标。

输出格式

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

样例

样例输入

4 2
1 2 7 3
6 5 8 3
7 8 10 5
9 6 13 9

样例输出

17

数据范围与提示

1≤n≤5001\leq n\leq5001n500
1≤k≤131 \leq k \leq 131k13

Source/Category