| Codeforces Round 574 (Div. 2) |
|---|
| Закончено |
Сегодня Денис проводит в ЛКШ клуб анонимных геометров. Он заготовил для клуба $$$n$$$ выпуклых многоугольников, пронумерованных от $$$1$$$ до $$$n$$$. Он планирует предложить участникам клуба посчитать суммы Минковского этих многоугольников. А именно, он планирует дать $$$q$$$ заданий, в $$$i$$$-м из них нужно посчитать сумму Минковского многоугольников с номерами от $$$l_i$$$ до $$$r_i$$$ включительно.
Суммой Минковского двух множеств $$$A$$$ и $$$B$$$ называется множество $$$C = \{a + b : a \in A, b \in B\}$$$. Можно доказать, что если $$$A$$$ и $$$B$$$ являются выпуклыми многоугольниками, то $$$C$$$ тоже будет выпуклым многоугольником.
Сумма двух выпуклых многоугольников Чтобы посчитать сумму Минковского $$$p$$$ многоугольников ($$$p > 2$$$), нужно посчитать сумму Минковского первых $$$p - 1$$$ многоугольников, а потом сумму Минковского результата и $$$p$$$-го многоугольника.
Для того, чтобы было удобнее проверять правильность выполнения заданий, Денис решил подготовиться и посчитать количество вершин в сумме Минковского для каждого задания. Помогите ему сделать это.
В первой строке дано одно целое число $$$n$$$ — количество выпуклых многоугольников, которые подготовил Денис ($$$1 \le n \le 100\,000$$$).
Далее дано описание $$$n$$$ выпуклых многоугольников. Описание $$$i$$$-го многоугольника начинается с целого числа $$$k_i$$$ — количество вершин в $$$i$$$-м многоугольнике ($$$3 \le k_i$$$). После чего в $$$k_i$$$ строках даны по два целых числа $$$x_{ij}$$$, $$$y_{ij}$$$ — координаты вершин $$$i$$$-го многоугольника в порядке обхода против часовой стрелки ($$$|x_{ij}|, |y_{ij}| \le 10 ^ 9$$$).
Гарантируется, что многоугольники не содержат трех последовательных вершин, лежащих на одной прямой. Суммарное количество вершин в многоугольниках не превышает $$$300\,000$$$.
В следующей строке одно целое число $$$q$$$ — количество заданий ($$$1 \le q \le 100\,000$$$). В следующих $$$q$$$ строках дано описание заданий. Описание $$$i$$$-го задания содержит два целых числа $$$l_i$$$ и $$$r_i$$$ ($$$1 \le l_i \le r_i \le n$$$).
Для каждого задания выведите одно целое число — количество вершин в сумме Минковского многоугольников с номерами от $$$l_i$$$ до $$$r_i$$$.
3 3 0 0 1 0 0 1 4 1 1 1 2 0 2 0 1 3 2 2 1 2 2 1 3 1 2 2 3 1 3
5 5 6
Пояснение к примеру:
Первый, второй и третий многоугольники из тестового примера 
Суммы Минковского первого и второго, второго и третьего и всех трех многоугольников соответственно
