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