🔒 Max rectangle area in given points

[tame grail]

Problem
You are given N points on a plane. Coordinates of each of them are integers from 0 to 10^5 inclusive. Each point is chosen randomly, equally likely among all possible points and independently of the others; in particular, points may coincide.
Choose four points at the vertices of a rectangle with horizontal and vertical sides and measure its area: what is the biggest area you can get?
Input format

N
x_1 y_1
x_2 y_2
...
x_N y_N
``` where `1 <= N <= 300'000` and `0 <= x_i, y_i <= 10^5`.
I am also given 2 examples: 6 points `(1, 1), (1, 3), (3, 1), (3, 3), (4, 1), (4, 3)` for which the answer is 6 and a file with 140k+ points with a big answer.

So first obviously I thought of doing what I'm told - choosing all possible four points, which would be O(N^4) and is way too slow. Then thought of choosing two points - the ones on the rectangle's diagonal and then checking if 2 other points exist, which is O(N^2 * log(N)) (log for checking if there's a point in a set) and is still too slow. The best I've got is sorting by the area of a rectangle formed by the point and origin (0, 0) (so sort by `x*y`) and then iterating `i = 0 .. N - 1` and `j = N - 1 .. i` and if the "theoretical maximum area" for either `i` or `j` is less than the already found maximum area, I break. This still runs way too slow for the 140k lines example. My code: https://paste.pythondiscord.com/SCBA.
Also I'm curious why would this be pointed out "Each point is chosen randomly, equally likely among all possible points and independently of the others". Maybe it's just to throw me off.

[stiff mesa]

@tame grail

Python help channel opened

Remember to:

• Ask your Python question, not if you can ask or if there's an expert who can help.
• Show a code sample as text (rather than a screenshot) and the error message, if you've got one.
• Explain what you expect to happen and what actually happens.

:warning: Do not pip install anything that isn't related to your question, especially if asked to over DMs.

Closes after a period of inactivity, or when you send !close.

[rough summit]

Maybe I am overcomplicating things and such algorithms are surely not in my area of expertise. I am thinking of something I recently learnt at school called "divide et impera" which is a concept that would imply to break the problem into sub-problems until you cannot break it any further. You would do this via reccursion and I was thinking that you could narrow down your list into chunks of 8 points (for example), find the maximum rectangle area in both, eliminate the other 8 points from these 2 chunks (4 points from each chunk) and then combine the chunks, and you would eliminate again 8 points and then combine again. I am not sure if this would increase speed but it would technically allow you to verify multiple areas in parallel.

and if you have 140k+ lines you might as well implement multi threading which again implies the concept of running in parallel so your computer runs the the same idea for multiple lines simulteanously

[tame grail]

The code is submitted and then tested on another machine so I believe I can't do multithreading. But I'll look into the divide and conquer approach, thanks.

[rough summit]

my pleasure

[shell igloo]

wouldn't the biggest area be found with the two points furthest away from each other?

for example, for the 6 points you gave, the two points furthest apart are (1, 1) and (4, 3). labelling these as x1, y1 and x2, y2, you can get the connecting points as x1, y2 and x2, y1.

if that fails then go one step down and try the same find furthest strategy again

anything wrong with my idea?

[shell igloo]

is that just merge sort but adapted for this tactic?

[shell igloo]

time complexity is probably really really bad

[stiff mesa]

Python help channel closed

This help channel has been closed and it's no longer possible to send messages here. If your question wasn't answered, feel free to create a new post in #1035199133436354600. To maximize your chances of getting a response, check out this guide on asking good questions.