ENG  RUSTimus Online Judge
Online Judge
Online contests
About Online Judge
Frequently asked questions
Site news
Problem set
Submit solution
Judge status
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests

Romanian Open Contest December 2001

About     Problems     Submit solution     Judge status     Standings
Contest is over

G. Lazy Snail

Time limit: 1.0 second
Memory limit: 64 MB
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
Problem Author: Mugurel Ionut Andreica
Problem Source: Romanian Open Contest, December 2001
To submit the solution for this problem go to the Problem set: 1173. Lazy Snail