P3357 Longest k-Overlap Segment Set Problem

Given a set $I$ of $n$ open line segments in the plane $x-O-y$, and a positive integer $k$. Design an algorithm to select a subset $S \subseteq I$ such that, for any point $p$ on the $x$-axis, the number of open line segments in $S$ that intersect the line $x = p$ does not exceed $k$, and $\sum\limits_{z\in S} |z|$ is maximized. Such a subset $S$ is called the longest $k$-overlap set of open line segments of $I$. The value $\sum\limits_{z\in S} |z|$ is called the length of the longest $k$-overlap segment set. For any open line segment $z$ with endpoints $(x_0, y_0)$ and $(x_1, y_1)$, its length $|z|$ is defined as: $$|z|=\lfloor\sqrt{(x_1-x_0)^2+(y_1-y_0)^2}\rfloor$$ Given the open line segment set $I$ and the positive integer $k$, compute the length of the longest $k$-overlap open segment set of $I$.

The first line contains $2$ positive integers $n$ and $k$, denoting the number of open line segments and the allowed overlap count. The next $n$ lines each contain $4$ integers, giving the coordinates of the $2$ endpoints of an open line segment.

Output the computed length of the longest $k$-overlap segment set.

Constraints: $1 \leq n \leq 500$, $1 \leq k \leq 13$, and all coordinates are within the `int` range. Translated by ChatGPT 5