POINPOLY - Editorial

editorial
, , , , ,
41

The setter’s solution gives a proof of it.

1 Like
42

You can actually prove that you will always find at least n / 10 points. See the setter’s solution described in the editorial for a proof of it.

43

Say that the lower y coord is 2.3 , and upper y coord is 2.8. What will your algo do here? Keep in mind that you can intersect the edge at non integral points. Omitting the decimal may cause point to lie out of polygon.

44

for that i have used

if(lower_y>higher_y) continue;

isn’t that sufficient , as it will skip this case and continue further

45

Thanks for sharing this :slight_smile:

46

can u explain me what u exactly did as i tried almost the same thing but it was WA.

what i did was find the leftmost x and rightmost x

loop through i = lx+1 to rx-1

then for each i , find where the vertical line intersects lower_y coordinate and upper_y coordinate.

then from floor(lower_y)+1 to ceil(higher_y)-1 store all the

values until it reaches our desired result.

47

you need to count from floor(lower_y+1.0) to ceil(higher-1.0)

48

From the question: No three vertices are collinear.

49

Firstly, the approach is correct- its only taking in mid point which will always lie inside polygon. He cannot get 2 same mid points from same starting/base vertex. He is taking one vertex, finding mid point of all vertices from that, it will give him N/10 points then and there. The only edge case where it fails is, where the mid point lies outside due to the loss f decimal/truncation of decimal.

Why is it weak test cases?

50

Its weak because even after failing on some edge cases the user is getting 70 points.

51

Yeah. I am very much interested in knowing that N=10 testcase in the first subtask which failed almost all the random techniques. Can @admin share that testcase?

52

I had the same question. How does 2 points being in the same hole prove that the midpoint is integral ?

53

@pavitra_ag (agni) just make a small change

for(long long int j=i+1;j<=i+8;j++)

54

you should not start j from i as it will be a[0]+a[0]/2 in the very first scenario resulting wrong answer …

55

@zizx @dollarakshay x and y can have 4 scenarios

O O

E O

O E

E E

now if there are four holes and there are 5 pigeons

then as author mentioned that 2 of them will go to the same hole

it means that the 2nd one which is going to the same hole will

resemble the same property as that of 1st one

i.e if O O goes the 2nd again O O will go their sum = E E hence E/2 E/2 will be an integer

similarly if O E goes then O E will go to the same hole

their sum = E E hence E/2 E/2 will be integer

this much i understood

56

Oh now I get it. Basically it says that there can only be 4 kinds of numbers:

x-ODD, y-ODD

x-ODD, y-EVEN

x-EVEN, y-ODD

x-EVEN, y-EVEN

So this means that if you have 5 points, 2 of them need to fall into one of these groups. So adding 2 numbers from the same group and dividing by 2 will always be an integer

(odd+odd)/2 = Integer

(even+even)/2 = Integer
57

hmm… right

58

No points may coincidence but fortunately non of first n/10 points u found coincided.may be test cases are weak.

59

If we could find if a point is inside a convex polygon in O(logN),couldnt we just run bfs from any vertex without dividing it into triangles?

Please @kushal101 if u could say if its possible or not.

60

can you please explain to me why doing j=i+1 works?
All I was doing was to pick 10 points then next 10 points and so on.
If I start from j=i+1 I never pick the first point.
A little help :slight_smile: