Hi all,
This is one of the problems from a hiring contest which is now over. Can someone help me in this?
Given $$$N$$$ lines, no 2 lines are collinear/parallel, none of the lines is parallel to y-axis and atmost 2 lines can intersect at a point. Clearly, these lines divide the 2-D plane into various regions. Given a single point $$$P$$$, determine the region where it belongs to.
I don't have any sample or constraints on $$$N$$$. I wrote some $$$O(N^2)$$$ solution(wrong) and it wasn't giving TLE. The only thing I could figure out after the contest was this. Can someone provide an easy and efficient solution?
Auto comment: topic has been updated by Samarth12 (previous revision, new revision, compare).
I think you are asking half-plane intersection?
Yes, I realized this after seeing IceKnight1093 comment. Thanks
For each line in the input, find out whether the point lies above or below it. You now have $$$N$$$ half-planes, and the region you're looking for is their intersection. Intersecting $$$N$$$ half-planes can be done in $$$\mathcal{O}(NlogN)$$$ (cp-algorithms page for reference).
Thanks.
Which company asks such tough problems in hiring challenges?
when rating of problem is more than CTC
Alternative solution:
Obviously, the region is convex. Do divide & conquer on the range $$$[0...2 \pi]$$$. For an angle $$$\alpha$$$ find the first intersection of a ray from point $$$P$$$ at angle $$$\alpha$$$. If for a given range both endpoints intersect on the same line, stop the recursion. This will work in $$$O(kn \log \epsilon ^{-1})$$$, where $$$k$$$ is the size of the answer. It can be optimized to $$$O(kn \log{n/k})$$$ I guess with some careful implementation.