DPMAX - Dot Product Maximization

no tags 

Given two vectors, a = ( xa, ya ), b = ( xb, yb ), their dot product is defined as follows:
dp( a, b ) = xa*xb + ya*yb.

Given N vectors in the plane, find a pair for each of them (among those given in the input) such that the dot product of the vector and its pair is maximal. You may pair a vector with itself too.

Input

The first line of input contains a single integer N ( 1 <= N <= 200000 ).
Each of the next N lines contain a pair of real numbers, xi and yi (0 <= |xi|, |yi| <= 100000), representing the i-th vector. xi and yi will be rounded to 3 decimal places.

Output

Output N lines, i-th one containing the maximal dot product for the i-th vector from the input rounded to 3 decimal places.

Example

Input:
4
0.000 1.000
0.000 2.000
1.000 1.000
0.000 0.000

Output: 
2.000
4.000
2.000
0.000

Explanation: Pair the first vector with the second, the second with itself, third with itself or with the second, and the last one with any of them.


hide comments
ujzwt4it: 2017-06-29 19:47:05

What kind of rounding of is to be used for a case like
123.456500--123.456 or 123.457

Last edit: 2017-06-29 21:15:15
Caesum: 2011-08-22 15:29:14

in the question it says 'x and y will be rounded to 3 decimal places', so is that no longer true?
answer: It's still true, I would have removed that otherwise.

Last edit: 2011-01-25 15:01:42
gustav: 2011-08-22 15:29:14

All test cases changed due to Shaka's discovery about faulty data. All people who got AC by now won't loose it... However, all the new submissions will need to be 100% precise (that is, you may not assume double or long double precisions will be good enough :)).

Shaka Shadows: 2011-08-22 15:29:14

Are the values in the input given with 3 decimal places too???

answer: yes

Last edit: 2011-01-11 14:09:24

Added by:gustav
Date:2010-12-23
Time limit:0.100s-0.600s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:own problem