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

Реформа

Реформа

На одній чудовій площині з декартовою системою координат з давніх давен була розміщена дуже консервативна країна. У цій країні з давніх давен було \textbf{N} міст, пронумерованих послідовними цілими числами від \textbf{1} до \textbf{N}. У порівнянні з нескінченністю площини міста, навіть дуже великі, дуже невеликі, тому ми будемо вважати їх точками на площині. Координати \textbf{i}-го міста --- (\textbf{X_i}, \textbf{Y_i}). Координати довільних двох міст різні. Ніякі \textbf{3} міста не лежать на одній прямій лінії. Деякі пари міст з'єднані двосторонніми дорогами. Кожна дорога --- це відрізок прямої лінії, який з'єднує деякі два міста. Відомо, що з кожного міста виходить рівно \textbf{3} дороги. Ніяка дорога не з'єднує місто саме з собою. Між кожною парою міст може бути не більше однієї дороги. Так йшли справи у цій країні з незапам'ятних часів, і нікому навіть не приходило до голови що-небудь змінити. Але ось пройшла біда --- до влади прийшов ліберальний король! І проблеми не заставили себе чекати -- негайно було видано указ про реформу дорожного сполучення у країні. Було наказано прибрати деякі дороги так, щоб у результаті: \begin{itemize} \item З кажного міста виходило рівно \textbf{2} дороги. \item Кут повороту між двома дорогами, які виходять із одного і того ж міста, був строго меншим \textbf{60} градусів. \item Ніякі дві дороги не перетинались ніде, крім як у містах. \end{itemize} Кут повороту між двома дорогами обчислюється наступним чином. Нехай з міста \textbf{B} дороги йдуть у міста \textbf{A} і \textbf{C}. Тоді кут повороту між ними дорівнює зовнішньому куту при вершині \textbf{B} у трикутнику \textbf{ABC} (див. рисунок). \includegraphics{https://static.e-olymp.com/content/92/92d2fc7497b5e546101170e331444d312807f563.jpg} Реалізацію реформи було доручено міністру транспорту. Саме йому належить вирвшити, які дороги видалити, а які залишити. Бажаючи догодити королю, серед усіх можливих способів вирішення поставленої королем задачі, міністр хоче вибрати такий, у якому максимальний з кутів повороту між двома дорогами із одного і того ж міста мінімальний. \InputFile Перший рядок вхідного файлу містить ціле число \textbf{N}. Кожен з наступних \textbf{N} рядків містить \textbf{5} цілих чисел. Перші два числа у \textbf{i}-му з цих рядків --- це \textbf{X_i} і \textbf{Y_i}. Наступні три числа --- це номери міст, з якими \textbf{i}-те місто спочатку з'єднано дорогами. Всі числа у вхідних даних цілі. \textbf{4} ≤ \textbf{N} ≤ \textbf{200}, \textbf{N} --- парне, \textbf{-10^5} ≤ \textbf{X_i}, \textbf{Y_i} ≤ \textbf{10^5}. Координати ніяких двох міст не співпадають. Ніякі \textbf{3} міста не лежать на одній прямій лінії. Кожне місто з'єднано дорогами рівно з \textbf{3}-ма містами. Між парою міст може бути не більше однієї дороги. Ніяка дорога не з'єднує місто саме з собою. Довільні два кути повороту (не обов'язково при одному місті) у країні до реформи відрізняються не менше ніж на \textbf{10^\{-5\}} градуса. Довільни кут повороту у країні до реформи відрізняється від кута у \textbf{60} градусів не менше ніж на \textbf{10^\{-5\}} градуса. \OutputFile Якщо поставлені королем вимоги виконати неможливо, виведіть єдиний рядок, що містить "\textbf{Minister's life is short :(}" (без крайніх лапок). Символи \textbf{’}, \textbf{:} та \textbf{(} мають \textbf{ASCII}-коди \textbf{39}, \textbf{58} і \textbf{40} відповідно. Інакше виведіть спосіб розв'язання задачі, який слід вибрати міністру, у вигляді \textbf{N} цілих чисел, відокремлених пропусками. Якщо \textbf{i}-те із виведених чисел рівне \textbf{j}, це означає, що міністру слід видалити дорогу між містами \textbf{i} та \textbf{j}.
Ліміт часу 2 секунди
Ліміт використання пам'яті 64 MiB
Вхідні дані #1
4
0 0 2 3 4
41 0 1 3 4
0 42 4 2 1
43 44 2 3 1
Вихідні дані #1
Minister's life is short :(
Автор Іван Метельський
Джерело Зимова Школа, Харків 2011, День 7