Help, POINPOLY February Long Contest - 2018

general
,
1

Hello all,

Can anyone help me out? I am trying to upsolve POINPOLY using the approach of dividing the given vertices into four groups :-

  1. x:even,y:even
  2. x:odd,y:odd
  3. x:even,y:odd
  4. x:odd,y:even

After doing this i am just finding the mid point of line segments formed by any two vertices of same group (as it will have integer coordinates). Now, as per my thinking the mid-point of line segment formed by any two vertices of the polygon lying in the same group out of these four shall lie inside the polygon and so there should not be any need to check if it lies inside the polygon but when i submit the code without checking this, i get WA, link to that code of mine is :- Solution: 17444855 | CodeChef

However when i check whether the mid-point lies inside or not and then submit, I get TLE as expected in some of the cases :- Solution: 17444843 | CodeChef

Can someone help me out with this, like where i am going wrong, is there any thing wrong with my approach etc and most importantly why we need to check for the mid point to lie inside the polygon if in case it’s required.

2

there may be a case when the pair is adjacent so their point may lie on the edge not strictly inside

3

Yes, you are right. Thanks for the help :slight_smile:

4

There may be cases when the mid points of two different line segments are the same. In such a case, your program might print the same point twice, resulting in a wrong answer.