Samarth12's blog

Easy solution?
By Samarth12, history, 3 years ago, In English

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?

  • Vote: I like it
  • +17
  • Vote: I do not like it

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by Samarth12 (previous revision, new revision, compare).

→ Reply
»
3 years ago, # |
  Vote: I like it +9 Vote: I do not like it

I think you are asking half-plane intersection?

→ Reply
»
3 years ago, # |
  Vote: I like it +11 Vote: I do not like it

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).

→ Reply
»
3 years ago, # |
  Vote: I like it +12 Vote: I do not like it

Which company asks such tough problems in hiring challenges?

→ Reply
»
3 years ago, # |
  Vote: I like it +42 Vote: I do not like it

when rating of problem is more than CTC

→ Reply
»
3 years ago, # |
  Vote: I like it +15 Vote: I do not like it

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.

→ Reply