Link : Problem
Thank you!
1 Like
[DISCLAIMER: I got a wa for this]
This is my approach:
The lowest and highest possible intersection points are around y = ±10^9. So we will run a binary search
with these as the limits.
We can write a function that takes a line y = mid as input and returns true if there are <= k intersection points below it and false otherwise. We will use this in our binary search.
To find the number of intersection points, first find all the x coordinates on the line y = mid which are intersection of this line with each of the n lines. Then sort these x coordinates to get a sequence of points.
My approach to find number of intersections below y=mid is for each point x in the sequence, count number of lines with a smaller angle theta with x axis to the left of it. This can be done in nlogn for all lines with a BIT or BST with some extra information stored at each node. Sum of all of them will give total number of intersections.
Another approach would be to compare the order of x coordinates for the lines y=mid with y=-infinity. If two lines intersect between -infinity and mid, then their order will be swapped in the two orders. This is equivalent to finding number of inversions and can be done in nlogn
Total complexity O(n logn log(10^11))
1 Like