| Submit | All submissions | Best solutions | Back to list |
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.
| 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 |
hide comments
|
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 |
|
|
2011-08-22 15:29:14 Caesum
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 |
|
|
2011-08-22 15:29:14 gustav
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 :)). |
|
|
2011-08-22 15:29:14 Shaka Shadows
Are the values in the input given with 3 decimal places too??? answer: yes Last edit: 2011-01-11 14:09:24 |
RSS