Roger, having figured out how to reason in two dimensions, has crafted a tricky puzzle for Victor to crack.
Roger has highlighted several lattice points in the ~xy~-plane and wants Victor to find the rectangle with maximum area inside that has vertices among the highlighted points!
Victor takes a look at this task and scoffs. It's just a line sweep problem, what's so tricky about that?
However, Roger points out to Victor that the rectangle need not be axis-aligned. The rectangles, much like Roger, can be tilted.
Is Victor tilt-proof?
~4 \le N \le 1500~
For at most 20% of full credit, ~N \le 500~.
~\left|x_i\right| \le 10^8~
~\left|y_i\right| \le 10^8~
All ~(x_i, y_i)~ are distinct.
The first line will contain a single integer, ~N~.
Each of the next ~N~ lines will contain two space-separated integers ~x_i~ and ~y_i~, indicating that Roger has highlighted point ~(x_i, y_i)~.
Print, on a single line, the maximum area of a rectangle with lattice points among the highlighted points. It is guaranteed that a non-degenerate rectangle exists.
8 -2 3 -2 -1 0 3 0 -1 1 -1 2 1 -3 1 -2 1