ok…
in poinpoly what i did was a horizontal line sweeping from left_x+1
to right_x-1 but it gave me wrong answer
https://www.codechef.com/viewsolution/17389361
probably due to wrong floor and ceil values calculation…
&& thanks taran for the editorial !!
Well, im not much in c++, so i cant exactly point out any bug in ur code.
And its no problem, i had the editorials written yesterday night only, but had class till 5 today, so got late in posting.
For POINPOLY , a simple technique is to find the centroid of the polygon and then simply finding the mid pts of each of the vertices and the centroid. This gave 70 pts and somehow failed for testcase 1 which turned out to be N=10 when I checked with assertions.That case had to be dealt separately.
for POINPOLY : I have another observation and it worked but i don’t know whether it’s fully correct or not(may be the test cases are weak)?
My observation : since all the co-ordinates have integer value, so, minimum height of the polygon can be (n - 4)/2 . How? : since the polygon is convex so, maximum two points have same y co-ordinate and similarly in worst case the upper part(the farthest from this point) has also two points having same y co-ordinate and now since we are considering the farthest point so, we can assume that there are almost equal number of points on both side of the line(line joining the farthest point) and so, we have atleast (n - 4)/2 points having different y co-ordinates and at worst case their differences are ‘1’. so, minimum height will be (n - 4)/2. Now, the solution is easy as we have to find only N/10 (far less than ~ N/2 points and we know that our line lies completely inside the polygon. so, we can iterate on integer y co-ordinates and get our points. Now, the question arises what about x co-ordinate ? How do we claim that it’s value is also an integer? Well, for this what i have done is I started from middle point and go on traversing in both direction one by one and i thought that this works because we are considering two farthest points and similarly we can claim that the width of the polygon at the middle is at worst (N - 4)/2 and hence truncating to the nearest x co-ordinate will not make the point lie outside the polygon!
If someone will find something wrong then please let me know 
For POINPOLY I tried to find out points only on lines joining vertices because there will be N*(N-1)/2 lines so I can easily get floor[N/10] points. For finding points on lines joined by integral points, I used the slope of lines. But the problem is when I implemented this solution I got WA for only second last case. @taran_1407 it would be really helpful if you could find the bug in my code or point out a mistake in my approach (Link to my JAVA Solution). During the contest, I solved the problem by Shuffling my set of points that I had collected while traversing on lines in hope that my code is printing some wrong points not all and it got AC. Here is code with shuffling for N=11 and which got AC.
it is O(log n), i m using two different function, one for calculating cos(nx) and other for calculating sin(nx) but sin(nx) use already computed value from the map
or you can look at this solution https://www.codechef.com/viewsolution/17401989 in which i m using just one function and make only one call at n/2
Thank you
There's nothing bad in swallowing pride to ur code as long as ur code gets AC.
Thats so lovely <33333.
roken clock alone kept me busy whole contest,
I spent 1 day trying to pass the last TC. I thought O({Log_2}^{2}N) will be fine. I was so naive 
I really hated to deal with that case separately, but well, desparate times call for desparate emasures XD. And I was there thinking its just me stuck on that damn N=10 case. XD
That case also had a N=10. They had included some “special” figures to hack/fail many solutions. Try to use brute force if N\le100 and see.
for CARPTUN
I have used the logic of pipelining, where the process which takes longest time decides the overall time spent.
so calculate the toll which takes longest time. and multiply it with (c-1) cars
It seems surprisingly fine to me. Can you code the same and submit in C++? To rule out any language difference in this.
For POINPOLY, I used the fact that centroid lies inside the triangle. And with PHP I proved that [n/10] distinct lattice points exists. But when implementing it I faced some issues.
My first
[2],I couldn't find the mistake. (Can you find?, Thanks in advance)
But when I rewire the code, I used long long every where instead of int, it passed. Here's my
Yeah, but long is necessary only when I add more than 3 coordinates as Each coordinate is <10^9 which comes inside int. So it is sufficient to put Long long for temp1, temp2
Basically, I segregated the corrdinates into 9 types depending on the values mod 3,sk that I can guarantee that the triangle formed by three points will have its centroid as a lattice point. So I used pos[x%3][y%3]=make_pair(x,y).and iterated through the vector and found the centroid.
Have a look at this solution of Pointpoly problem (it’s not mine) https://www.codechef.com/viewsolution/17306405