ENG  RUSTimus Online Judge
Online Judge
О системе
Часто задаваемые вопросы
Новости сайта
Архив задач
Отправить на проверку
Состояние проверки
Исправить данные
Рейтинг авторов
Текущее соревнование
Прошедшие соревнования

1173. Lazy Snail

Ограничение времени: 1.0 секунды
Ограничение памяти: 64 МБ
Here, in Romania, all snails are lazy. Take Wally the Snail, for example. He has to visit N friends which are located at distinct coordinates in the plane. But since he is so lazy, he doesn't want to leave his house. He said that he will go visit his friends if someone can show him the right path to follow.
He wants to leave his house, visit all of his friends exactly once and then return to his house. Between 2 friends' houses or between his house and a friend's house, he walks on the straight line which connects them. 'Is that all ?', someone asked. Wally realized that this would be too easy, so he added that, during his trip, no two line segments along which he travels should cross (except for every 2 consecutive segments, which cross at one end). You must find a path for Wally, so he can go visit all of his friends (although he doesn't want to).

Исходные данные

On the 1st line of input, there will be 2 real numbers: X and Y, separated by a blank, representing the coordinates of Wally's house. On the 2nd line, there will be an integer number: N (2 ≤ N ≤ 1000), the number of friends Wally has to visit. On the next N lines, there will be 3 numbers, separated by blanks: X , Y and ID. ID will be an integer number, representing the ID of one of Wally's friends. X and Y will be 2 real numbers, representing the coordinates of Wally's friend's house (they will be given with at most 3 decimal digits and will be in the range -100000 .. 100000).
All IDs are unique, between 1 and N. No 3 friends (including Wally) have their houses on the same straight line.


You should output N+2 lines: the IDs of the friends whose houses Wally is about to visit, in the order he visits them. Start with Wally's ID, continue with the ID of the friend he visits first and so on. Finish with Wally's ID. Wally has ID 0.
If there is no solution, then print a single line, containing the number -1.


исходные данныерезультат
0 0
3 3 1
6 0 2
6 2 3
Автор задачи: Mugurel Ionut Andreica
Источник задачи: Romanian Open Contest, December 2001