Məsələlər
Орлы и дятлы
Орлы и дятлы
В лесу находятся гнезда орлов и дятлов. Когда у орлов вылупились птенцы, они решили огородить "детскую площадку", на которой молодежь могла бы резвиться под надзором взрослых особей. Орлы хотят, чтобы детская площадка имела максимально возможную площадь, и чтобы дополнительно выполнялись следующие условия:
\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}.
Giriş verilənləri #1
3 0 0 3 0 0 4 1 1 1
Çıxış verilənləri #1
0