MarioYC's blog

By MarioYC, 12 years ago, In English

Although I didn't passed this problem during the contest, I really enjoyed it.

The reason is I never I hadn't thought before about solving "point in a polygon" queries in a more efficient way other than using O(n) algorithm for every query.

But after getting hacked, and trying to optimize my code, I noticed something nice. If we use the ray tracing algorithm for one point inside a convex polygon, then we worry bout at most four sides of the polygon every time (I assume we are using the Ray casting algorithm), and this combines really nicelly with a sweep line approach, in which you only keep the interesting sides, and discard them when they can't be intersected by the points that follow.

Implementation : 1398412

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