I am trying to solve https://community.topcoder.com/stat?c=problem_statement&pm=2384&rd=4755
My code is here http://pastebin.com/Y1GtwPg8
My solution fails in last two given test cases . how to handle those cases? Help please . Thanks in advance 
Hi @biprotip
A video game approach, for the fun :). Tribute to Mario !! Complexity is O(N*N).
Step 1: compress the coordinates. Their values belong now to [0…M], with M<=N
Step 2: multiply the coordinates by 2, to allow separation in the algorithm
Step 3: set up a bitmap. map=new int[M][M]. Fill with zero value./
Step 4: draw the lines of your polygon on the bitmap with value 1.
Now you have two ways to finish the job. Choose your path, between subtilety and pure power…
- The elegant way:
Step 5elegant:
Take your point (x,y). If value == 1 then the answer is BOUNDARY. If not, take the point just on the right (x+1,y). And look at the number of points with value 1 you encounter when going from (x+1,y) to (x+1,0). If this number is odd, then your initial point is INTERIOR. Otherwise EXTERIOR.
The counting works because all the vertices are on even coordinates. So if (x,y) is interior with x even, so is (x+1,y). And when going from (x+1,y) to (x+1,0) you will never encounter vertices (because they have even x coordinate)
- The brute force
Step 5brutal: Look at the points with maximum y. Amongst them, take the one with minimum x. That gives you point xmin,ymax. You are sure that xmin+1,ymax-1 belongs to the INTERIOR. Start a floodfill from this point, with value 2.
Step 6: Juste look at colors to tell INTERIOR (color=2), BOUNDARY (color=1), EXTERIOR (color=0)