Dear codeforces,
I am writing to seek help from everyone in cf to find the optimal time complexity for the following problem.
Given the following inputs,
The first line contains an integer $$$n$$$, the total numbers of points in the 2D-plane.
The next $$$n$$$ lines contain 2 integers each. The $$$i^{th}$$$ ($$$0 \leq i < n$$$) of them contains 2 space-separated integers $$$p_{i_x}$$$, $$$p_{i_y}$$$ , the x and y coordinates of point $$$p_i$$$. Note that $$$i$$$ is also the id of the point $$$p_i$$$.
The next line contains an integer $$$q$$$, the number of queries.
The next $$$q$$$ lines contain 2 integers each.The $$$j^{th}$$$ ($$$1 \leq i \leq q$$$) of them contains 2 space-separated integers $$$l_j$$$, $$$r_j$$$, a range of points from the id $$$l_j$$$ to id $$$r_j$$$ ($$$0 \leq l_j, r_j < n$$$ and $$$3 \leq r_j - l_j + 1 \leq n$$$ ).
Please output the answer with the following requirements:
For the $$$j^{th}$$$ line, which is the $$$j^{th}$$$ query ($$$1 \leq j \leq q$$$), find and output the area of the convex hull of the set of points $$$p_i$$$ in range $$$l_j \leq i \leq r_j$$$ of the id.
Example
| Input 1 | Output 1 |
|---|---|
| 7 1 1 3 0 2 2 3 5 5 4 6 2 4 2 3 2 6 2 7 1 7 | 10 11.5 14 |
l=2, r=6 => area=10
l=2, r=7 => area=11.5
l=1, r=7 => area=14
