The developers of the e-Lite game made it possible for each player to adjust the parameters of his spaceship as he wants.
Initially each player has a spaceship with n empty slots on its body. The player can either put up a jet engine in a slot or use this slot for a cargo module. Each slot can be used for an engine of a specific type, i.e., with a certain direction and power.
The spaceship’s controlling system is designed so that all the engines can be either simultaneously turned on at full power or simultaneously turned off.
If the engines accelerate the spaceship in different directions, it can happen that the installation of all the engines imparts to the spaceship a smaller acceleration than the installation of only a part of them. That is why a player should think where to install engines to get the maximum acceleration.
Input
The first line contains the number n (1 ≤ n ≤ 1 000) of empty slots on the spaceship’s body.
The i-th of the following n lines contains integers xi and yi (−106 ≤ xi, yi ≤ 106), which are the coordinates
of the vector of acceleration imparted to the ship by the i-th engine.
Output
For each i from 1 to n, output in a separate line the value of the maximum acceleration of a ship with exactly i engines.
The absolute or relative error of each answer should not exceed 10−6.
Sample
input | output |
---|
3
3 -2
-3 -2
0 4
| 4.000000
4.000000
0.000000
|
Problem Author: Alexander Ipatov
Problem Source: Ural Sport Programming Championship 2013