How can i solve the problem?

general
,
1

There are an interesting problem https://community.topcoder.com/stat?c=problem_statement&pm=2384&rd=4755

Here is the tutorial https://www.topcoder.com/community/data-science/data-science-tutorials/geometry-concepts-using-geometry-in-topcoder-problems/

I cant understand the line “the test point is on the interior if, and only if, the ray crosses the boundary an odd number of times.”
why odd number of time when the polygon vertices are in even number ?
It will be a greate help if u explain it to me . Thanks in advance :slight_smile:

1 Like
2

I don’t know more .But what I think …is :
It means : if a ray passes a boundry of a polygon for the first time , it gets inside the polygon .when it again passes the boundry it comes out .similarly for the third time when it passes the boundry it again becomes the test point which is on the interior of the polygon i.e inside the polygon.

3

Just do it

4

@biprotip: It’s explained on wikipedia. https://en.wikipedia.org/wiki/Point_in_polygon. The tricky part is when the ray you cast encounter a vertex. Because a vertex belongs to 2 edges, it can make your calculation wrong.

For the specific problem in topcoder you mentioned, because the edges are either horizontal or vertical, you can solve it using bitmaps :slight_smile: like in old videogames…I posted a solution here: https://discuss.codechef.com/questions/77444/how-to-solve-that