最大面积矩形
Maximum area rectangle
给定的一组点 (x[1]; y[1]), (x[2]; y[2]), ..., (x[n]; y[n]) 。我们需要找到我们可以获得的最大矩形面积。矩形的顶点应该在点集中。此外，矩形不必与轴对齐。例如，(1; 1), (2; 2), (2; 0); (3; 1) 的答案是 2。
n <= 1300; -10^9 <= x[i], y[i] <= 10^9.
有人可以帮我解决这个问题吗？我的解决方案是蛮力 O(N^3)，它给出了 TLE。我select一些三点，找到第四点。
Every pair of points determines a line L, which has a slope m and an intercept c. (Ignore vertical lines for now.) Instead of considering the intercept, let's work with a different quantity that gives much the same information: The distance d(L) between the line and the origin, i.e., the length of a line segment R perpendicular to L and connecting L to the origin. Additionally, we can talk about the "displacement" of a point along L: We can say that the point p on L where it meets R has displacement 0, and the point on L that is x "above" p (has distance x from p and higher y coordinate) has displacement x, with negative displacements for points "below" p. In fact, we don't need the intercept or d(L) to define the displacement of a point with respect to a line L -- just the line's slope. Define disp(m, q) to be the displacement of point q on a line with slope m.
Suppose a, b, c, d are the vertices of a rectangle, with sides ab, bc, cd and da. Observe that the line containing ab has the same slope m as the line containing cd, and (disp(m, a), disp(m, b)) = (disp(m, d), disp(m, c)). So the only 4-tuples of vertices that we need to test are those comprised of pairs of vertex pairs like ab and cd -- vertex pairs having the same slope and displacement pairs. Furthermore, one side length (shared by ab and cd) is equal to |disp(m, b) - disp(m, a)|, and the other side length will be |d(Lab) - d(Lcd)|, where Lab and Lcd are the lines containing the line segments ab and cd, respectively.
To find these 4-tuples of vertices efficiently:
- For all pairs of vertices i, j:
- Let L be the line passing through i and j. Compute its slope m and distance d(L) from the origin. Also compute disp(m, i) and disp(m, j). If disp(m, i) <= disp(m, j), add the tuple (m, disp(m, i), disp(m, j), d(L)) to an array Z.
- Sort Z lexicographically. This will place all point pairs lying on lines of the same slope and having equal displacements in a contiguous block, ordered by increasing d(L).
- Scan through the array, looking for block boundaries -- positions k at which any of the first three tuple elements changes. Let prev be the last such k found (initially, prev = 0). For each such k:
- Compute (Z[k-1][3] - Z[prev][3]) * (Z[k-1][2] - Z[k-1][1]). This is the area of the largest rectangle having a pair of sides with slope Z[k-1][0] and length (Z[k-1][2] - Z[k-1][1]). If this is greater than the maximum rectangle size found so far, update it.
This algorithm takes O(n^2 log n) time and O(n^2) space.
给定的一组点 (x[1]; y[1]), (x[2]; y[2]), ..., (x[n]; y[n]) 。我们需要找到我们可以获得的最大矩形面积。矩形的顶点应该在点集中。此外，矩形不必与轴对齐。例如，(1; 1), (2; 2), (2; 0); (3; 1) 的答案是 2。
n <= 1300; -10^9 <= x[i], y[i] <= 10^9.
有人可以帮我解决这个问题吗？我的解决方案是蛮力 O(N^3)，它给出了 TLE。我select一些三点，找到第四点。
Every pair of points determines a line L, which has a slope m and an intercept c. (Ignore vertical lines for now.) Instead of considering the intercept, let's work with a different quantity that gives much the same information: The distance d(L) between the line and the origin, i.e., the length of a line segment R perpendicular to L and connecting L to the origin. Additionally, we can talk about the "displacement" of a point along L: We can say that the point p on L where it meets R has displacement 0, and the point on L that is x "above" p (has distance x from p and higher y coordinate) has displacement x, with negative displacements for points "below" p. In fact, we don't need the intercept or d(L) to define the displacement of a point with respect to a line L -- just the line's slope. Define disp(m, q) to be the displacement of point q on a line with slope m.
Suppose a, b, c, d are the vertices of a rectangle, with sides ab, bc, cd and da. Observe that the line containing ab has the same slope m as the line containing cd, and (disp(m, a), disp(m, b)) = (disp(m, d), disp(m, c)). So the only 4-tuples of vertices that we need to test are those comprised of pairs of vertex pairs like ab and cd -- vertex pairs having the same slope and displacement pairs. Furthermore, one side length (shared by ab and cd) is equal to |disp(m, b) - disp(m, a)|, and the other side length will be |d(Lab) - d(Lcd)|, where Lab and Lcd are the lines containing the line segments ab and cd, respectively.
To find these 4-tuples of vertices efficiently:
- For all pairs of vertices i, j:
- Let L be the line passing through i and j. Compute its slope m and distance d(L) from the origin. Also compute disp(m, i) and disp(m, j). If disp(m, i) <= disp(m, j), add the tuple (m, disp(m, i), disp(m, j), d(L)) to an array Z.
- Sort Z lexicographically. This will place all point pairs lying on lines of the same slope and having equal displacements in a contiguous block, ordered by increasing d(L).
- Scan through the array, looking for block boundaries -- positions k at which any of the first three tuple elements changes. Let prev be the last such k found (initially, prev = 0). For each such k:
- Compute (Z[k-1][3] - Z[prev][3]) * (Z[k-1][2] - Z[k-1][1]). This is the area of the largest rectangle having a pair of sides with slope Z[k-1][0] and length (Z[k-1][2] - Z[k-1][1]). If this is greater than the maximum rectangle size found so far, update it.
This algorithm takes O(n^2 log n) time and O(n^2) space.