DPMAX - Dot Product Maximization
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.
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 N lines, i-th one containing the maximal dot product for the i-th vector from the input rounded to 3 decimal places.
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.
What kind of rounding of is to be used for a case like
in the question it says 'x and y will be rounded to 3 decimal places', so is that no longer true?
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 :)).
Are the values in the input given with 3 decimal places too???