PROBLEM LINK:
Author: Ritik Mittal
Tester: Nitin Gupta
Editorialist: Ritik Mittal
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