Задача №114759. Полёт над озером
Петя любит делать снимки местности при помощи квадрокоптера. Однажды он отправился в путешествие к живописным берегам озера. Озеро может быть представлено в виде не обязательно выпуклого многоугольника на плоскости. Петя запустил квадрокоптер над озером на небольшом расстоянии от поверхности воды и сделал несколько снимков. Если квадрокоптер находится над точкой озера с координатами \((x', y')\), то на снимке будут видны все точки плоскости, \(y\)-координаты которых не превосходят \(y'\). Для каждого снимка Петю интересует суммарная площадь частей озера, которые видны на этом снимке. Но он очень занят обработкой фотографий и просит Вас помочь с этой задачей.
В первой строке задано целое число \(n\) (\(3 \leq n \leq 100\,000\)) — количество вершин многоугольника, описывающего озеро.
Каждая из следующих \(n\) строк содержит по два целых числа \(x_i, y_i\) (\(0 \leq x_i, y_i \leq 10^9\)) — координаты вершин многоугольника в порядке обхода.
Гарантируется, что озеро представляет собой корректный невырожденный многоугольник, то есть не содержит самопересечений и самокасаний, также никакие три подряд идущие вершины многоугольника не лежат на одной прямой. Обратите внимание, что многоугольник может быть невыпуклым .
Следующая строка содержит целое число \(q\) (\(1 \leq q \leq 100\,000\)) — количество снимков.
Каждая из следующих \(q\) строк содержит по одному целому числу \(y'_i\) (\(0 \leq y'_i \leq 10^9\)) — \(y\)-координату точки озера, над которой находился квадрокоптер, чтобы сделать \(i\)-й снимок.
Выведите \(q\) чисел \(s_i\) — суммарную площадь озера, которую видно на \(i\)-й фотографии. Можно доказать, что ответ всегда представим в виде несократимой дроби \(P \over Q\). Вам нужно вывести \(s_i \equiv P \cdot Q^{-1} \ (~\mod \ 10^9 + 7)\). Иными словами, вам необходимо найти такое \(s_i\) (\(0 \leq s_i < 10^9 + 7\)), что \(s_i \cdot Q \equiv P \ (~\mod \ 10^9 + 7)\).
7 3 0 3 3 1 3 1 4 0 4 0 0 2 2 4 1 3 2 4
750000006 6 3 7
11 5 7 8 7 9 5 12 7 14 7 14 5 12 5 12 2 1 2 1 9 3 9 10 5 8 6 3 13 7 2 1 9 4
33 500000062 45 11 61 55 0 0 61 22