King Brian is looking at rectangles!
He has a list of of ~N~ points ~(x_1, y_1), (x_2, y_2), (x_3, y_3), \dots, (x_N, y_N)~ and can select any four at random. If the four points form the four corners of an axis aligned rectangle, he writes down the area.
What is the largest possible area he can get from selecting four random points?
Note: axis aligned means that the four lines that form the rectangle are all either horizontal or vertical (aligning with the ~x~ and ~y~ axes respectively).
For all subtasks:
~4 \le N \le 2 \times 10^3~
~1 \le |x_i|, |y_i| \le 2 \times 10^4~
No two points will be the same.
Subtask 1 [15%]
~1 \le N \le 50~
Subtask 2 [70%]
~1 \le N \le 500~
Subtask 3 [15%]
No additional constraints.
The first line will contain the integer ~N~.
The next ~N~ lines will each contain two space separated integers: ~x_i~, ~y_i~.
Output one line, the maximum possible area of an axis aligned rectangle King Brian can get from selecting four random points. If no rectangles can be formed, print ~0~.
9 1 1 5 5 7 7 5 7 7 5 10 10 5 10 10 5 20 20
There are two possible rectangles that can be constructed with the ~9~ points:
- From ~(5, 5)~ to ~(7, 7)~ with an area of ~4~
- From ~(5, 5)~ to ~(10, 10)~ with an area of ~25~
Thus the answer is ~25~.