| Author: | I. Ludov | Time limit: | 1 sec | |
| Input file: | input.txt | Memory limit: | 256 Mb | |
| Output file: | output.txt |
Spaceship Behemoth was sent to conquer the Gamma Pisces star system.
System has N planets numbered from 1 to N. The planets may be considered stationary and located on one plane. Every planet is guarded by a military space station, with the orbit in the same plane.
Some of these stations rotate around their planets clockwise, others — counterclockwise. Station orbits are ellipses. They can intersect, but cannot touch. No orbit lies entirely inside of another.
Spaceship is so huge and strong that it can easily destroy any object it encounters. Too bad, but to make it so powerful, engineers had to limit its navigational and maneuvering capabilities. It can either orbit a planet on the same orbit as one of the stations or very rapidly accelerate and decelerate to jump from one orbit to another one. The trajectory of such jump is a straight line tangent to both source and destination orbits.
To destroy a space station the ship must enter its orbit with the rotation direction opposite to that of the station. If it encounters the station while on the orbit, the station will be immediately smashed to pieces. If it has to depart an orbit before reaching its prey, it leaves a nuclear proximity mine, which will finish the business for sure.
After the destruction, the orbit of the former station gets polluted by much debris dangerous even for our mighty ship. It still can safely travel across these already visited orbits, but cannot take them for later maneuvers.
Your program must plan an assault on Gamma Pisces, which will result in destruction of all of its military stations. Behemoth will emerge from the subspace on orbit of Gamma Pisces Prime (planet number 1) and start its mission there.
Input file contains integer N — the number of planets, followed by N orbit descriptions. Each description consists of 5 integers x1 y1 x2 y2 c d, where (x1, y1) and (x2, y2) specify coordinates of ellipse foci, c is the length of semi-major axis and d equals 1 if station rotates clockwise and − 1 if counterclockwise.
Output file must contain N integers — planet numbers in order of visiting. If several solutions exist, output lexicographically minimal one. If the solution does not exist, output a single integer − 1.
| No. | Input file (input.txt) |
Output file (output.txt) |
|---|---|---|
| 1 | |
|
| 2 | |
|