I have been trying to solve this problem on SPOJ-- http://www.spoj.com/problems/DPMAX/
After 6hrs of trying and 16 wrong submissions, I have finally decided to seek some help.
Brief Overview
We are given n vectors. The problem asks us to calculate the maximum dot product of every vector with any other vector including itself. The absolute value of x and y coordinates is less than equal to 10^5. And there are 2*10^5 vectors to process.
My approach
1.Take these vectors as points. Find their convex hull.
2. The answer for all vectors will be the dot product with another vector with its end as a point of convex hull found
3.Hypothesis--The maximum dot product for a vector lying in first quadrant should be with a vector which forms the upper right hull of the convex hull, similarly for a second quadrant it should be with a vector which forms the upper right hull and so on.
4.So vectors in the four different quadrants are separated into 4 different groups and the vectors are sorted to be in anti-clockwise order for each group.
5.Indices of Right-most, top-most, bottom-most, left-most points of hull are found.
6. Two-pointer approach is applied with one pointer being the starting of the sorted group and the other being points on the hull.(left-most,bottom-most...)
Pairing will be of the form--First quadrant vectors with right-most point, Second quadrant vectors with the top most point and so on. 7.For the vector in consideration we move to the next point in counter-clockwise direction only if the dot-product of the next point with the vector is greater than the dot-product with current point, otherwise we move to the next vector.
This approach worked for this problem-http://codeforces.net/problemset/gymProblem/100886/H My solution--http://codeforces.net/gym/100886/submission/28148901 However the vectors were only lying in first-quadrant for this question.
I have generated lot of random test cases and checked with brute-force solution and it had no diff at all. Here is my solution--http://www.spoj.com/status/ns=19708915
It would be great if you could tell me if my approach is wrong or some test case where my solution fails.
Thanks a lot for helping
