# PROBLEM LINK:

* Author:* Ritik Mittal

*Nitin Gupta*

**Tester:***Ritik Mittal*

**Editorialist:**# DIFFICULTY:

MEDIUM-HARD.

# PREREQUISITES:

DP, Geometry, 2-pointers

# PROBLEM:

choose some line among the N that have at least k intersection points among themselves and minimizes the cost, i.e., (Power_{max}−Power_{min}) among chosen lines.

# QUICK EXPLANATION:

We can sort the lines according to the power. And use a 2 pointer approach to get every range of lines that have at least k points of intersection. And the minimum such cost is the answer.

# EXPLANATION:

The intersection of 2 lines segment can be easily found in O(1) time. see here .

Now for any segment/range of lines, we can use a dp kind of approach to get a contribution for that segment, To add a line R under current consideration, we check for every line in the current segment whether it intersects, say line C intersect with line R we add one to dp[C]. To remove a line L from current consideration just subtract dp[L]. See here for code