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](https://cp-algorithms.com/geometry/point-location.html). Can someone provide an easy and efficient solution?↵
↵
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](https://cp-algorithms.com/geometry/point-location.html). Can someone provide an easy and efficient solution?↵
