Its weak because even after failing on some edge cases the user is getting 70 points.
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?
I had the same question. How does 2 points being in the same hole prove that the midpoint is integral ?
you should not start j from i as it will be a[0]+a[0]/2 in the very first scenario resulting wrong answer …
@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
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 = Integerhmm… right
No points may coincidence but fortunately non of first n/10 points u found coincided.may be test cases are weak.
I see everyone considered it as MEDIUM level Question,but i don’t think so.Though my approach is a bit similar with setter’s solution,but i just use IF ELSE and FOR LOOP only,so for a beginner one can easily deals with it,rather than left it by thinking the vector approach or other algorithm’s
https://www.codechef.com/viewsolution/17430200
Please see my solution and respond if any query,thanking you.
@zizx
lets see that i am taking n*(n-3)/2 diagonal of the polygon.Then if (x1+x2)=even and (y1+y2)=even at the same time then you will find the perfect mid loint of that diagonal in the form of integer.
If you take any two vertex and find their mid point in form of integer by negletting the decimal points or floating poing there will be some case where error will occur.
1 Like
@souradeep1999 that was a good approach u r choosing everytime pure integers . with no loss of precision
thanks for the explanation
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.
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 
I talked to @admin regarding that. I dont think it will help much, since the polygons in that TC arent “small”. Example, one of the cases where many solutions failed was-
10
-479724248 168812047
-479723521 168812070
-479723209 168812080
-479721714 168812128
-479720573 168812165
-479718272 168812240
-479717385 168812269
-479716591 168812295
-479715554 168812329
-479714732 168812356
Basic idea is, huge change in x axis with very small change in y axis. Your code passed this TC though, but quite many failed at it (esp those who took mid points)
For those who used mid point trick for their answers, the corner cases were like-
10
-479724248 168812047
-479723521 168812070
-479723209 168812080
-479721714 168812128
-479720573 168812165
-479718272 168812240
-479717385 168812269
-479716591 168812295
-479715554 168812329
-479714732 168812356
A simple figure illustration will be like-
![alt text][1]
(PS: Not an art student, cant draw a perfect decagon like that XD)
The crux of these tests is, big change of x (or y) co-ordinate, and very minor/very small change in the y (or x) co-ordinate. Due to this, when calculating midpoint, a +-1 error in y co-oord results in WA (meaning, the decimal part is the deciding factor).
If you truncate the decimal, you fail in the first (upper figure), if you round up the decimal, you fail in the lower one.
[1]: https://discuss.codechef.com/upfiles/Presentation1.jpg
Just keep it simple.
After getting the idea how to check whether a given point is inside the given polygon or not,I adopted the following strategy.
Since it is a convex polygon ,say for a vertex (x,y) it is guaranteed that one of (x,y-1),(x,y+1),(x-1,y),(x+1,y) will definitely lie inside the polygon.So just iterate through all given n points and break out when you get [n/10] points.
My solution : My-Solution-POINPOLY
But your basic reasoning is not correct.
We can create a square, which is convex, with corners at (\pm 1, \pm 1). The only internal integer point is at (0,0), but doesn’t have the form (x \pm 1, y) or (x, y \pm 1).
A more general counter-example follows from multiplying the points in the sample data by some matrix like \left( \begin{matrix} 1000 & 999999 \\ 1 & 1000 \end{matrix}\right). The result is a long narrow convex polygon. The internal integer points are not close to the vertices.
1 Like
if (x-1,y-1) and (x+1,y+1) i think all the cases should come under it