Дан выпуклый многоугольник на плоскости. Посчитайте, пожалуйста, количество треугольников, образованных его вершинами, которые содержат данную точку на плоскости. Гарантируется, что точка не лежит на сторонах и диагоналях многоугольника.
В первой строке содержится число n — количество вершин многоугольника (3 ≤ n ≤ 100000). Далее идет описание многоугольника: n строк с координатами очередной вершины в порядке обхода по часовой стрелке (целые числа x, y, по модулю не превосходящие 109). Гарантируется, что данный многоугольник невырожденный и выпуклый (никакие три точки не лежат на одной прямой).
Следующая строка содержит число t (1 ≤ t ≤ 20) — количество точек, для которых нужно посчитать ответ. Далее идут описания точек: t строк с координатами очередной точки (целые числа x, y, по модулю не превосходящие 109).
Выходной файл должен содержать t чисел, каждое на отдельной строке, i-е число — ответ для i-й точки.
Пожалуйста, не используйте спецификатор %lld для чтения или записи 64-х битовых чисел на С++. Рекомендуется использовать поток cin (также вы можете использовать спецификатор %I64d).
4 5 0 0 0 0 5 5 5 1 1 3
2
3 0 0 0 5 5 0 2 1 1 10 10
1 0
5 7 6 6 3 4 1 1 2 2 4 4 3 3 2 3 5 5 4 2
5 3 3 4
3000 ms 256 Mb Правила оформления программ и список ошибок при автоматической проверке задач