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

Ural Championship 2013

About     Problems     Submit solution     Judge status     Standings
Contest is over

H. E-Lite

Time limit: 2.0 second
Memory limit: 64 MB
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 (−106xi, 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

inputoutput
3
3 -2
-3 -2
0 4
4.000000
4.000000
0.000000
Problem Author: Alexander Ipatov
Problem Source: Ural Sport Programming Championship 2013
To submit the solution for this problem go to the Problem set: 1978. E-Lite