Codeforces Round #706 Diamond Miner - Greedy

Solution

Simple Greedy. Pair the points who have smaller absolute value as soon as we can.

We have prove below：

Let's see if there are 4 points：(x,0), (x+a,0), (0,y), (0,y+b). Both x, y, a and b equal or bigger than 0. It's not hard to prove that, [(x,0),(0,y)] [(x+a,0),(0,y+b)] is lesser than [(x+a,0),(0,y)] [(x,0),(0,y+b)]。

So for any combination which is not the best solution, we can do the things blow：select two points. So we can see if these two points can be change with the result before. Then if we continuously do this, then we will get the best solution.

Rather than get a random combination and use $n^2$ way to get best solution. We can sort the points by absolute value first.

Code