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.
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
|
|
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?
|
|
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???
|
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 |