План шпионской сети
В штабе Джонни нашел большую карту, на которой несколько точек были отмечены двумя цветами — зеленым либо красным. Тогда он не придал находке большого значения, однако, позже оказалось, что на карте были изображены два проекта по переоборудованию шпионской сети, показанные, соответственно, разными цветами.
Основная идея переоборудования заключается в том, чтобы распределить агентов между несколькими точками. Каждая точка управлялась бы непосредственно штабом. В каждой точке может находиться несколько агентов. В таком случае точка указывалась на карте ровно столько раз, сколько агентов должно было там находиться.
Территория, контролируемая множеством точек, определяется следующим образом: это наименьшее по площади выпуклое множество точек на плоскости, которое содержит все точки из исходного множества точек. В случае, если все точки множества лежат на одной прямой, то контролируется наименьший по длине отрезок этой прямой, содержащий все точки исходного множества.
Джонни четко помнил, где были размещены точки, однако какие из них соответствовали первому проекту, а какие — второму, он вспомнить никак не мог. Еще он помнил, что оба проекта реализовать было нельзя, так как территории, контролируемые точками из различных проектов, пересекались.
Последний факт, который смог вспомнить Джонни — точек одного цвета было намного больше, чем точек другого цвета. Джонни стало интересно, как точки могли быть распределены между проектами. Формально, Джонни хочет найти такое распределение точек, чтобы территории, контролируемые точками разных цветов, пересекались, а разность между числом точек, принадлежащих разным проектам была наибольшей.
Входные данные
В первой строке задано целое число n (4 ≤ n ≤ 10^5) - число количество точек. В каждой из следующих n строк содержатся по два целых числа x[i] и y[i] (-10^9 ≤ x[i], y[i] ≤ 10^9) - координаты точек, указанные на карте. Гарантируется, что искомое разбиение существует.
Выходные данные
В первой строке выведите целое число m - размер меньшего по размеру множества точек. Во второй строке выведите m чисел - индексы точек, входящих в это множество. Если оптимальных ответов несколько, разрешается вывести любой.