Hello friends, I am trying to solve this task from topcoder: Link to PowerSupply
I have read the editorial but I cannot undertand how to choice the best parallel line to one of the two diagonals. The vertical and horizontal lines I know how to get the answer, but how can I find the 'best parallel line' to one of the diagonals ?
I'm very confused, can you explain with some details please ?
Ps: I know how to find the distance from a point to a line.
Thanks.
You can rotate all points by 45 degrees. Then to find answer for diagonals you have to find answer for vertical and horizontal lines.
rem's solution
Thank you Alias, I have solved this problem with a bit of pain... :D
My solution follow: http://pastebin.com/x2REAmNC