Problem H
Sultan and Khairun Shundori
Input: Standard Input
Output: Standard Output
Flowerland is in
festive mood. Their princess Khairun Shundori will choose her life-partner
today. Princes and handsome young men from distant and neighboring countries have
gathered in the capital. Princess will interview them one after one. Among
these young men, there’s Sultan from Codeland.
The interviews
start. One after one, failed young men get out of King’s castle in great
disappointment. Then comes our hero Sultan. He impresses the Princess with his
amazing grace and smartness. He passes all the tests the Princess poses before
him. Almost impressed, the Princess gives him one last task – he have to
collect roses from all the gardens in the city for her.
Seems like an easy task, doesn’t it?
Especially when Sultan has already pin-pointed every garden in the city using
Google Maps. But there are some catches – as soon as Sultan gets out of the
castle, the losers will try to kill him out of jealousy. Sultan will be followed
and followed in great number. So he can’t afford to take the risk of going
through a point he previously visited i.e. he can’t intersect his previous
path. Then again, he wants to finish this task as soon as possible. So he will
always run from one garden to another in a straight line.
Input
There will be at most 50
test cases. Each test case starts with an integer n, number of
points of interest (one of them is the castle and the rest are gardens) [3≤n≤1000].
Each point of interest will be specified by the integer (x,y)
co-ordinate of that point [-10000≤x,y≤10000]. No two
points of interest will be located in the same co-ordinate. The castle will
always be the first point in input. Sultan has to start and end his journey in
the Castle. Input is terminated by a case where n equals 0.
Output
For each test case, you have to output
a sequence of indices of points of interest in one line that will ensure the
task. Any sequence that doesn’t violate the conditions will be accepted. Points
will be indexed from 0 in the output. If there is no valid sequence for the
input, you have output “no solution”.
Sample Input Output
for Sample Input
|
4 0 0 1 0 1 1 0 1 5 5 5 10 0 10 10 0 10 |
0 1 2 3 0 0 1 2 3 4 0 |
Problem
Setter: Sabbir Yousuf Sanny
Special
Thanks: Manzurur Rahman Khan