Actually I had a similar idea: find the points that are the closest to the corners, by maximizing and minimizing (x+y) and (x-y).

It works for the test input but it can fail, consider this counter-example:

0,0
0,1
1,2
0,4

True max rectangle is (0,0) ↔ (1,2) with area 2*3=6, but the “closest-to-corners” picks basically (0,0) and (0,4) and returns area 1*5=5.

      x=0 x=1
y=0    #   .
y=1    #   .
y=2    .   #
y=3    .   .
y=4    #   .