Easy solution?

Revision en2, by Samarth12, 2021-07-01 20:19:28

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?

Tags #hiringchallenge, #geometry

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en3 English Samarth12 2021-07-01 20:21:27 0 (published)
en2 English Samarth12 2021-07-01 20:19:28 41 (saved to drafts)
en1 English Samarth12 2021-07-01 20:12:29 641 Initial revision (published)