How to solve that?

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 :slight_smile:

alt text

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)

//