\(2^{th}\) round, November \(7^{th}\) 2015
You have most definitely heard the legend of King Arthur and the Knights of the Round Table. Almost
all versions of this story proudly point out that the roundness of the Round Table is closely related
to Arthur’s belief of equality among the Knights. That is a lie! In fact, Arthur’s choice of table is
conditioned by his childhood traumas.
In fact, Arthur was forced to clean up quadratic tables from a young age after a tournament in
pi\(ck-up\) sticks^{1} had been played on them. After the tournament, typically there would be a bunch of
sticks on the table that do not touch each other. In the spirit of the game, the organizers issued
strict regulations for the table cleaners. More precisely, the sticks on the table need to be removed one
by one in a way that the cleaners pull them in the shortest way towards the edge of the table
closest to where they are currently sitting. They also mustn’t rotate or touch the other sticks while
doing this (not even in the edge points).
In this task, we will represent the table in the coordinate system with a square that has opposite points
in the coordinates (0,0) and (10 000, 10 000), whereas the sticks will be represented with straight line
segments that lie within that square. We will assume that Arthur is sitting at the edge of the table
lying on the \(x-ax\)is. Then the movement of the stick comes down to translating the line segment
along the shortest path towards the \(x-ax\)is until the stick falls offthe table (as shown in the image). It
is your task to help Arthur determine the order of stick movements that meets the requirements from
the previous paragraph.

In test cases worth 40% of total points, it will hold 1 ⩽\(N\) ⩽10. In test cases worth 60% of total
points, it will hold 1 ⩽\(N\) ⩽300.

The first line of input contains the integer \(N\) (1 ⩽\(N\) ⩽5 000), the number of sticks on the table. Each
of the following \(N\) lines contains four integers \(x\)1, \(y\)1, \(x\)2, \(y\)2 (0 ⩽\(x\)1, y1, x2, y2 ⩽10 000) that denote
the edge points of a stick.

The first and only line of output must contain spa\(ce-se\)parated stick labels in the order which they
need to be taken offthe table. A stick’s label corresponds to its position in the input sequence.
If there are multiple possible solutions, output any of them.
^{1}A game that involves carefully moving sticks.
\(2^{th}\) round, November \(7^{th}\) 2015

생성자가 기록되지 않았습니다.

출처 COCI 2015/2016 Contest 2