### PROBLEM LINK:

Practice

Contest: Division 1

Contest: Division 2

**Setter:** Bogdan Ciobanu

**Tester:** Xiuhan Wang

**Editorialist:** Taranpreet Singh

### DIFFICULTY:

Hard

### PREREQUISITES:

Convex Hull, Rotating Calipers, Range Minimum Query (RMQ) and bucket decomposition.

### PROBLEM:

Given N points and Q queries (f,t) specifying range [f,t], find the maximum squared euclidian distance between any pair of points within the specified range.

### QUICK EXPLANATION

- Divide the points into buckets and build a convex hull for each bucket (preferably using Monotone Chain algorithm).
- Build an RMQ sparse table considering each block as one unit, rmq[i][j] representing the convex hull formed by points from blocks in the range [i,i+2^j-1]. Hulls should be merged in O(S) where S represent the size of the hull.
- Most distant point pair from a set of points can be easily found by using Rotating Calipers on the convex hull of the given set of points. To answer a query, make a convex hull consisting of points belonging to partially filled buckets and merge it into the appropriate pre-built convex hull from RMQ for intermediate blocks and calculate the answer.

### EXPLANATION

Let us solve a trivial problem first. Given a set of points, find the maximum distance between any pair of points.

**Lemma:** The pair of points having the maximum distance lie on convex hull formed by points.

**Proof:** Let us assume we have a point pair AB being the most distant point pair, Point A strictly inside the convex hull and point B on or inside convex hull. Lt us extend this line toward A till it intersects the border of the convex hull, say at segment CD. Now, it can be seen, that at least one of |BC| > |BA| or |BD| > |BA| holds, which contradicts the fact that points AB have the maximum distance. This contradicts our assumption. Hence, for the points to be most distant, both points shall lie on the convex hull.

Now, to find the maximal distance, we can use the rotating calipers technique, explained in brief below.

Let us have a pointer variable p and for every point indexed i, move it forward till the distance of (p+1)th point from the line formed by ith and (i+1)th point is more than distance of pth point from same segment, considering distance of pth and (p+1)th point from ith point. whenever moving from ith point to (i+1)th point, consider its distance of both these points from pth point. The maximum of all these is the distance of most distant point pair.

An important point to note is, that binary search is not going to work, as explained well here.

**Merging Convex hulls**

We merging convex hulls naively (assuming Monotone Chain algorithm is being used). In Monotone Chain algorithm, we find the points having leftmost and rightmost x-coordinate and build lower and upper convex hull separately. So, while merging, we can use merge-sort type technique to merge lower and upper hulls and removing the useless points in time proportional to the size of the convex hull.

Returning to original problem, we can build a RMQ sparse table, where RMQ[i][j] represent the convex hull formed by points in range [i, i+2^j-1] which can be easily rewritten as the convex hull formed by merging RMQ$[i][j-1] and RMQ[i+2^{j-1}][j-1]$. The details of RMQ can be found here.

Now, Let us evaluate the time complexity of this solution. During preprocessing, we have log(N) levels having N convex hulls. We can see, that merging convex Hull take time proportional to the size of convex hull, resulting in preprocessing time being O(N*log(N)*S) after which, each query may take O(S) time as both merging convex hull and calculating most distant point pair take O(S) time.

Now, the question is, what is the size of the convex hull? We have randomly generated points in the second sub-task while worst cases in the third sub-task. 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, MX = 2*10^5 in our case. This explains the difference in time complexity of the same solution for second and third sub-task. See references here and here.

Now, we see, though it may be sufficient with optimizations to pass this solution for the second subtask, it shall be hard to pass the final subtask. So, Let us optimize the preprocessing part to fit the time limit by bucket decomposition.

Let’s first divide all N points into blocks of size SZ and now, build RMQ considering each block as one position in RMQ. This way, to answer queries, we can use RMQ to find convex hull formed by points in intermediate blocks and naively build a temporary convex hull by points which lie in partially filled blocks (can be at most 2 for each query). We can merge these two blocks and calculate the answer for this block.

Now, Let us calculate the time complexity of this solution. If C = \lceil N/SZ \rceil, we can build RMQ on blocks in O(S*C*log(C)) time and answer each query in O(SZ+S) time, resulting in time complexity O(S*(N/SZ)*log(N) + Q*(S+SZ)). It works fast enough for SZ = sqrt(S*N*log(N)/Q).

**Editorialist solution**

The editorialist who like different solutions, choose to use graham scan as means of building and merging convex hulls as opposed to Monotone Chain algorithm in case of setter and tester solution. This slows down editorialist’s solution by log(S) due to the fact that for Graham scan, sorting by the polar angle is required while in Monotone Chain algorithm, merging convex hull can be done in merge sort type manner in O(S) for both lower and upper hulls. This is the reason Monotone Chain algorithm is preferred to Graham scan in this problem.

An interesting problem to try is GEOCHEAT.

### Time Complexity

Overall time complexity is O(S*(N/SZ)*log(N/SZ) + Q*(S+SZ)) where SZ is the block size chosen.

Space Complexity is O(N+S*(N/SZ)*log(N/SZ)).

### AUTHOR’S AND TESTER’S SOLUTIONS:

Setter’s solution

Tester’s solution

Editorialist’s solution

Feel free to Share your approach, If it differs. Suggestions are always welcomed.