409020: GYM103415 L Dynamic Convex Hull
Description
There are $$$N$$$ points.
You will be given $$$M$$$ queries. Each query will give you several points. You must answer the area of the convex hull of these points merged with the initial $$$N$$$ points.
InputThis problem contains multiple test cases.
The first line contains an integer $$$T$$$ ($$$1 \le T \le 10^5$$$) — the number of test cases.
For each test case:
The first line contains an integer $$$N$$$ ($$$3 \le N \le 2 \times 10^5$$$) — the number of the initial points.
Then $$$N$$$ lines follow. The $$$i$$$-th of them contains two integers $$$x_i,y_i$$$ ($$$|x_i|,|y_i| \le 10^9$$$) — the coordinate of the $$$i$$$-th initial point.
The next line contains an integer $$$M$$$ ($$$1 \le M \le 2 \times 10^5$$$) — the number of queries.
Then $$$M$$$ queries follow. For each query: the first line contains an integer $$$k$$$ ($$$1 \le k \le 10$$$) — the number of points in this query; then $$$k$$$ lines follow, the $$$i$$$-th of which contains two integers $$$x_i,y_i$$$ ($$$|x_i|,|y_i| \le 10^9$$$) — the coordinate of the $$$i$$$-th point in this query.
It is guaranteed that in all test cases, the sum of $$$N$$$ is no more than $$$10^6$$$, and the sum of $$$k$$$ is no more than $$$10^6$$$.
OutputFor each query in each test case, output $$$2 \times S$$$ in one line. $$$S$$$ indicates the area in this query.
It can be proved that $$$2 \times S$$$ is always an integer.
ExampleInput1 8 -1 2 -2 1 -2 -1 -1 -2 1 -2 2 -1 2 1 1 2 1 3 0 3 0 4 1 5Output
39