Задача №112910. Cheese
Крешо купил вкуснейший сыр с перцем, но Степану перец не нравится, поэтому он хочет отрезать кусок, на котором не было бы перца. Сыр имеет форму выпуклого многоугольника, а каждая перчинка является точкой внутри него. Степан режет сыр только 1 раз. Он выбирает две вершины многоугольника, не являющиеся смежными, и режет по диагонали, соединяющей их. Затем Степан забирает ту из получившихся частей, на которой нет перца (ни внутри, ни на границе).
Рисунок соответствует первому тесту. Пунктирной линией показан разрез Степана.
Напишите программу, которая определит, может ли Степан отрезать кусок без перца. Если он может это сделать, выведите максимальную площадь куска, который может отрезать Степан.
Первая строка входного файла содержит одно целое число N — количество вершин в многоугольнике. Каждая из следующих N строк содержит два числа x i и y i — координаты i -й вершины. Следующая строка содержит одно число M — количество перчинок. Каждая из следующих M строк содержит два числа x i и y i — координаты i -й перчинки.
Вершины многоугольника заданы в порядке обхода против часовой стрелки и образуют выпуклый многоугольник. Никакие две подряд идущие стороны не параллельны.
Все перчинки расположены в различных точках и внутри многоугольника (они не расположены на стороне или снаружи многоугольника).
Выведите одно число — удвоенную максимальную площадь (это число всегда целое). Если отрезать кусок без перца невозможно, выведите 0.
Система оценки:
- 12 баллов. 4 ≤ N ≤ 300 , 1 ≤ M ≤ 300 .
- 39 баллов. 4 ≤ N ≤ 3000 , 1 ≤ M ≤ 3000 .
- 49 баллов. 4 ≤ N ≤ 300 000 , 1 ≤ M ≤ 300 000 .
Во всех подзадачах координаты от - 10 9 до 10 9 .
5 0 1 3 0 4 2 2 3 0 3 3 2 1 3 1 3 2
4