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. <br/>↵
**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.<br/> ↵
**My approach**<br/>↵
1.Take these vectors as points. Find their convex hull.<br/>↵
2. The answer for all vectors will be the dot product with another vector with its end as a point of convex hull found <br/>↵
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.<br/>↵
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.<br/>↵
5.Indices of Right-most, top-most, bottom-most, left-most points of hull are found.<br/>↵
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...)<br/>↵
↵
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://mirror.codeforces.com/problemset/gymProblem/100886/H↵
My solution--http://mirror.codeforces.com/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
After 6hrs of trying and 16 wrong submissions, I have finally decided to seek some help. <br/>↵
**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.<br/> ↵
**My approach**<br/>↵
1.Take these vectors as points. Find their convex hull.<br/>↵
2. The answer for all vectors will be the dot product with another vector with its end as a point of convex hull found <br/>↵
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.<br/>↵
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.<br/>↵
5.Indices of Right-most, top-most, bottom-most, left-most points of hull are found.<br/>↵
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...)<br/>↵
↵
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://mirror.codeforces.com/problemset/gymProblem/100886/H↵
My solution--http://mirror.codeforces.com/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
