CHEFSPAG (40 points)

general
1

please share your algorithm for CHEFSPAG 40 points

2

i can share my approach for 40 points:
for 10 points it was trivial…just loop through every possible (i,j) and check whether or not its inside the polygon.

for 40 points: you must observe that for every line x+y=c (c is a constant), the value of F remains same. Also, since x,y<=10^4, c can be at max 2*10^4, this gives you an approach, that for every possible c, find points of intersection of line with segments of polygon, and count number of points inside the polygon.Cases may arise like when a line x+y=c cuts polygon at 1,2,3 (or may be more)points . What I did was to sort points by x co-ordinate and check whether mid-point of adjacent points lie inside polygon, if yes include all integer points co-ordinate in the range between the 2 coordinates, else only the end points.

The calculations can be simplified with clever observations like rotating co-ordinate system…but the main idea according to me was the observation of x+y=c .Hope it helps.

2 Likes
3

For 10 points, my code was giving TLE. :confused:

4

it shouldn’t…you could have just looped through all possible pairs…might be some other problem!

1 Like
5

For 10 points I precalculated F(k) and looped through every possible(i,j) and checked whether or not it was inside or on the boundary of polygon.
For checking if a point is inside or on the boundary of polygon,I used the code available at http://www.geeksforgeeks.org/how-to-check-if-a-given-point-lies-inside-a-polygon/

But the result was WA. Dont know why?
link- https://www.codechef.com/viewsolution/11513813

1 Like
6

hi akshayv3
in geekforgeek that code is wrong… because for point were place their line on vertices from right this say no in polygon while this point is in polygon … i change this code but i can not get acceptance

7

@ankesh18 used same idea. If any point (not neccesarily mid-point) in between two intersected adjacent points lies inside the polygon, then the whole points between them will lie inside polygon.
here’s my
Implementation.

1 Like
8

yaa…exactly…i wrote mid point for simplicity, but ya any point can be used.

9

should add 2 points:

  1. In above explanation i didnt mention about the recurrence F. It definitely needs to be pre-calculated. I skipped as I thought it was obvious.

  2. The geek for geek code doesn’t work for several cases.
    Hope it settles the confusion.

10

Geeks for geeks code to check if a point lies inside the polygon works, if extreme point is taken as (INF,p.y-1) instead of (INF,p.y) .

I did that and got 10 points

1 Like