Find axis-aligned rectangle with maximum area in a point set in the Euclidean plane On the plane $n$ points $(x_i, y_i)$ are marked. Select 4 points so that they define a rectangle with the greatest area and sides parallel to the axes.

Time limit for python is 10 seconds, for other programming languages - 2 seconds.

Input data:


in first string integer $n$, $(4 \leq n \leq 3000)$
in next $n$ strings pairs of integer coordinates $x_i\  y_i$ $(-10\ 000  \leq x_i,\ y_i  \leq 10\ 000)$


Output data:


4 different indices (numbers from $1$ to $n$), specifying the vertices of the rectangle.


I made in python, but even with tests of $n \leq 111$ it have TL.

n = int(input())
l = []
for i in range(n):
    a, b = map(int, input().split())
    l.append((a, b))

ans = [1, 2, 3, 4]
mS = 0

for i in range(0, n - 3):
    for j in range(i, n - 2):
        for k in range(j, n - 1):
            for t in range(k, n):
                r = [l[i], l[j], l[k], l[t]]
                w = sorted(r, key=lambda element:(element[0], element[1]))
                if w[0][0] == w[1][0] and w[1][1] == w[3][1] and w[3][0] == w[2][0] and w[2][1] == w[0][1]:
                    s = (w[1][1] - w[0][1]) * (w[3][0] - w[1][0])
                    if s &gt; mS:
                        mS = s
                        ans = [i + 1, j + 1, k + 1, t + 1]

ans = sorted(ans)
print(ans[0], ans[1], ans[2], ans[3])
Step 1. Sort all the points according to their $x$-coordinate - you will get an array of buckets, where each bucket contains a (sorted) list of points with the same $x$-coordinate. You can drop (or ignore in all subsequent steps) all the buckets, containing only single point.

Step 2. Define a mapping $M$, where the key will be a closed integer interval and the value - ordered set of integers. Scan all the buckets, created in the Step 1. For each bucket insert all the possible pairs of its $y$-coordinates into the mapping $M$ - their corresponding $x$-coordinates must be inserted into the set, corresponding to this interval:

function Insert(M, x, y0, y1)
  if mapping M contains element ([y0, y1] -&gt; S)
    insert x into set S
  else
    insert element ([y0, y1] -&gt; (x)) into mapping M


You can drop (or ignore in all subsequent steps) all the elements of the mapping $M$, for which their value set contains only a single number.

Step 3. The mapping M will contain elements like this:

$$([y_0, y_1] \rightarrow (x_0, x_1, ..., x_{m-1}))$$

The biggest rectangle with "vertical" side $[y_0, y_1]$ will have "horizontal" side $[x_0, x_{m-1}]$, so you can ignore all the middle elements of the ordered set. Finally, scan all the elements in the $M$ to find the element with largest rectangle area $A$:

$$A = (y_1 - y_0) \cdot (x_{m-1} - x_0) $$  

Number of intervals in $M$ is $O(n^2)$, so time to insert into the mapping will be $O(n^2log(n))$.