Блог пользователя azidoazideazide

Автор azidoazideazide, 5 лет назад, По-английски
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

I am looking forward to seeing your comments if you have suggestions and questions of this entry.
Thank you for reading!
P.S. : This is my first attempt at a blog. Please suggest edits wherever required!

Полный текст и комментарии »

  • Проголосовать: нравится
  • +91
  • Проголосовать: не нравится