1
$\begingroup$

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 > mS:
                        mS = s
                        ans = [i + 1, j + 1, k + 1, t + 1]

ans = sorted(ans)
print(ans[0], ans[1], ans[2], ans[3]) 
$\endgroup$
5
  • $\begingroup$ Can you put the reference to the original problem and explain properly how 4 points should define the rectangle. Do they have to be the 4 corners ? If you can also replace your python code with pseudo-code or just explain your method (even if it is simple brute-force), it would be perfect. $\endgroup$
    – Optidad
    Commented Jun 7, 2019 at 14:49
  • $\begingroup$ @Vince I can't put the link, the competition is closed. Right, my code just simple brute-force. It takes each 4 points and check does it rectangle with sides parallel to axes. This task does not go out of my head. I think there is some kind of algorithm to reduce the complexity of calculations. And points should be the 4 corners, yes. $\endgroup$
    – Evgeny
    Commented Jun 7, 2019 at 14:54
  • $\begingroup$ Okay without a link you can tell which competition it is so people can check it is actually closed. $\endgroup$
    – Optidad
    Commented Jun 7, 2019 at 15:01
  • $\begingroup$ @Vince contest.yandex.ru/contest/12350/enter/?lang=en $\endgroup$
    – Evgeny
    Commented Jun 7, 2019 at 15:03
  • $\begingroup$ I don't see any question, here. Note also that questions about coding are off-topic, here. $\endgroup$ Commented Jun 7, 2019 at 15:42

2 Answers 2

3
$\begingroup$

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] -> S)
    insert x into set S
  else
    insert element ([y0, y1] -> (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))$.

$\endgroup$
1
$\begingroup$

Sort the points indexes on increasing $x_i$ (time complexity $O(N\log N)$). Then, with one loop on this sorted list, you can create the following structure:

  • $GX$, list of sublists where points in the same sublist share the same $x$ value.
  • $AX$, array of size $n$ giving for any $i$ the index of the sublist that contains $i$ in $GX$.

Once it is done, sort every sublist of $GX$ on increasing $y$

Let's do the same for $y$, to obtain $GY$ and $AY$. So far time complexity is still $O(N\log N)$.

A valid rectangle of four points $a, b, c, d$ starting up left clockwise should have:

  • $AX[a] = AX[d]$
  • $AX[b] = AX[c]$
  • $AY[a] = AY[c]$
  • $AY[b] = AX[d]$

Now, let's do the nested loops using $GX$ and $GY$ to hardly reduce the number of rectangles to check:

  • Loop on all possible $a$
  • Loop on all $b$ in $GY[AY[a]]$
  • create two pointers $c$ and $d$ in respectively $GX[AX[b]]$ and $GX[AX[a]]$
  • evaluate in linear time all possible $c, d$ such that $y[c] = y[d]$ (it is possible as the GX are sorted by $y$)

Complexity should be $O(N^2)$, I am not sure about that.

As all the sublists are sorted, you can also know the maximum array reachable from the upper left corner in $O(1)$. So check the potentially large rectangles first and use a stop criterion.

You finally have a $O(N^2)$ complexity instead of your $O(N^4)$.

$\endgroup$
3
  • $\begingroup$ Two possible enhancements: First, eliminate all points with a unique x-coordinate or a unique y-coordinate, which then might lead to the elimination of more points. Second, iterate in an order that tends to find large areas first: In the first two loops, a and b must be in the same list with k elements. Iterate over a and b that are k-1 apart, then k-2 apart etc., this will tend to have a long side first. If you found a solution already, you may be able to proof that you can't find a rectangle with the side (a, b) and a larger area. Otherwise, ... $\endgroup$
    – gnasher729
    Commented Jun 8, 2019 at 19:16
  • $\begingroup$ ... when you iterate through the points c, d, you start with the points furthest away from a and b, and stop iterating once you know that the area of (a, b, c, d) cannot break the record so far. $\endgroup$
    – gnasher729
    Commented Jun 8, 2019 at 19:17
  • $\begingroup$ @gnasher729 absolutely, that is what I meant when I said check the largest rectangles first. I did not want to give all these precisions as it does not change time complexity and would make a lot harder my answer to understand. $\endgroup$
    – Optidad
    Commented Jun 8, 2019 at 19:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.