Блог пользователя Samarth12

Автор Samarth12, история, 3 года назад, По-английски

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?

  • Проголосовать: нравится
  • +17
  • Проголосовать: не нравится

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
3 года назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится

I think you are asking half-plane intersection?

»
3 года назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится

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

»
3 года назад, # |
  Проголосовать: нравится +12 Проголосовать: не нравится

Which company asks such tough problems in hiring challenges?

»
3 года назад, # |
  Проголосовать: нравится +42 Проголосовать: не нравится

when rating of problem is more than CTC

»
3 года назад, # |
  Проголосовать: нравится +15 Проголосовать: не нравится

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.