eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Орлы и дятлы

Орлы и дятлы

В лесу находятся гнезда орлов и дятлов. Когда у орлов вылупились птенцы, они решили огородить "детскую площадку", на которой молодежь могла бы резвиться под надзором взрослых особей. Орлы хотят, чтобы детская площадка имела максимально возможную площадь, и чтобы дополнительно выполнялись следующие условия: \begin{itemize} \item площадка являлась выпуклым многоугольником, в вершинах которого находились гнезда орлов; \item зная привычку дятлов все время долбить и опасаясь, что какой-нибудь дятел насмерть задолбает кого-нибудь из еще неокрепших птенцов, орлы хотят, чтобы на территории площадки (а также на её границе) не было гнезд дятлов. \end{itemize} Напишите программу, которая по заданному расположению гнезд орлов и дятлов находит оптимальное место для строительства детской площадки. \InputFile Входной файл содержит сначала число \textbf{N} (\textbf{3} ≤ \textbf{N} ≤ \textbf{100}) - количество орлов в лесу, затем \textbf{N} пар чисел, задающих координаты гнезд орлов, затем число \textbf{M} (\textbf{0} ≤ \textbf{M} ≤ \textbf{100}) - количество дятлов, и, наконец, \textbf{M} пар чисел, задающих координаты гнезд дятлов. Координаты каждого гнезда задаются парой целых чисел, каждое из которых по модулю не превышает \textbf{10000}. Никакие два гнезда не находятся в одной точке. \OutputFile В выходной файл выведите сначала число \textbf{K} - количество гнезд орлов, которые будут вершинами многоугольника, задающего детскую площадку, а затем \textbf{K} чисел - номера гнезд орлов, которые будут вершинами этого многоугольника (гнезда нумеруются начиная с \textbf{1} в порядке, в котором они заданы во входном файле). Гнезда должны быть перечислены в порядке обхода вершин многоугольника по или против часовой стрелки. Если построить площадку ненулевой площади не удастся, в выходной файл выведите одно число \textbf{0}.
Лимит времени 1 секунда
Лимит использования памяти 64 MiB
Входные данные #1
3
0 0 3 0 0 4
1
1 1
Выходные данные #1
0