If the points are carefully placed approximately on the circle, then the worst case for the hull size would include all points, not just MX^(2/3). If the points are consecutively numbered, then no matter how we split them into blocks the merged hulls would include all points in the range. I wonder if there was such test case.
I used a segment tree of convex hulls, which is probably slower that the proposed solution. So I had to make optimization for constants.
@shoom What I think the post meant, was that given a grid MX * MX, the maximum points I can place such that all the points constitute the convex hull cannot be generally more than MX^(2/3). And I think all these points will be approximately on a circle like you said, but due to integer coordinate constraints, it can never surpass MX^(2/3). This is just a possibility and I could be wrong.
I also built a segtree with convex hull of points in the subtree and used rotating calipers to find farthest points. I got 50 points. I also tried storing upper hull / lower hull and merging them but it didn’t get me any further. Unfortunately I don’t understand the trick related to bucket decomposition to make it work for the third case. I need to read about it a bit probably. 
thanks for posting this editorial!
It can be seen from research that the expected number of points in convex hull of N randomly generated points is roughly of the order of N^{1/3} while if we generate points carefully in MX∗MX grid, we can have up to around MX^{2/3} points in convex hull.
First of all, the bound for randomly generated points in a square in O(\log n), not O(n^{1/3}). This is present in the paper linked in the editorial. No reference for the case of carefully generated worst case is provided. Can you share that @taran_1407?
To @meooow:
The worst case is when the points form roughly a circle. However the placement of the points is a bit tricky but here is the idea:
For the case 0 <= x, y <= 200,000 generate all co-prime pairs x,y (x < y) where xx + yy < 79*79. That’s about 1500 of such pairs. Sort them by slope x/y, and also include [0,1] and [1,1]. Consider such x,y pairs as “edges” to use to construct 1/8 of a circle while using them in sorted order, starting with [0,1] and ending with [1,1] (the slope changes from 0 to 1). Repeat the process 8 times by flipping to construct the full circle. That’s about 12,000 points, and all of them are in the convex hull. Then add extra points (to reach 200,000 points) by placing them closely to the original points inside the circle. Then randomly shuffle their order.
To clarify the circle construction:
The few first co-prime pairs are [0,1], [1,78], [1,77], [1,76], …, [1/40], [1/39], [2/77], etc.
Then place points at:
x0,y0 = [0, 100000]
x1,y1 = [x0 + 0, y0 + 1] = [0, 100001]
x2,y2 = [x1 + 1, y1 + 78] = [1, 100079]
x3,y3 = [x2 + 1, y2 + 77] = [2, 100156]
...
@nima101 I couldn’t doit during the contest but it can be solved with segment tree of Convex_Hulls and no need of bucket decomposition.
Check the following submition: CodeChef: Practical coding for everyone . It uses the Convex Hull class of the Tester Solution as nodes of a segment tree.
What’s the reason of giving such problems? The main idea to build Segment Tree/Sparse Table of convex hulls was covered by the second subtask, which appeared as a problem on Codechef a year ago (CodeChef: Practical coding for everyone). The last subtask only needs googling a weird statement, or trying to squeeze your solution without knowing that it is actually correct.
The solve function in the setter’s solution looks like it is using 2 pointers? If it is indeed 2 pointers, then how is it correct? I saw this comment on the CF blog with the counter to the 2 pointer method to find the diameter of a convex hull.
If we can use merge sort tree type thing to merge to hulls why do we need RMQ then why cant we use segment tree to answer the queries?
I used CH in each node of segtree. During queries, i merged the relevent node’s segtree and computed the CH of this resulant set of ppints. I then computed the farthest point using o(n^2) bruteforce. (Stupid of me… I had thgt that rotating callipers would TLE… 
)this gets 50 pnts.
It matter, since the solution time is proportional to the convex hull size. The hull size (as percentage from the total number of points) is smaller for randomly generated points as majority of the points fall inside the convex hull rather than on it.
See the part of editorial discussing hull size. Time complexity of merging as well as rotating calipers is proportional to hull size.
Updated link.
See this blog for details. Number of points on Convex hull with lattice points - Codeforces
Ok thanks.
Here is no other problems. Moreover, no med-hard+ problems without FFT at all :((
Thank you!
Thanks!
Because using segtree, we shall have to merge logN hulls (logC hulls if using sqrt dec). But by RMQ, we need to merge only two hulls (three hulls if sqrt dec, border block elements). Using segtree would increase per query complexity by log(N)