maximum-area-rectangle-with-point-constraints-i

java

python

python3

mysql

mssql

oraclesql

csharp

javascript

typescript

bash

swift

kotlin

dart

golang

ruby

scala

rust

racket

erlang

elixir

pythondata

postgresql

cangjie

Algorithms

You are given an array <code>points</code> where <code>points[i] = [xi, yi]</code> represents the coordinates of a point on an infinite plane.

Your task is to find the maximum area of a rectangle that:

<ul>
	<li>Can be formed using four of these points as its corners.</li>
	<li>Does not contain any other point inside or on its border.</li>
	<li>Has its edges&nbsp;parallel to the axes.</li>
</ul>

Return the maximum area that you can obtain or -1 if no such rectangle is possible.

&nbsp;
Example 1:

<div class="example-block">
Input: points = [[1,1],[1,3],[3,1],[3,3]]

Output: 4

Explanation:

<img alt="Example 1 diagram" src="https://assets.leetcode.com/uploads/2024/11/02/example1.png" style="width: 229px; height: 228px;" />

We can make a rectangle with these 4 points as corners and there is no other point that lies inside or on the border. Hence, the maximum possible area would be 4.
</div>

Example 2:

<div class="example-block">
Input: points = [[1,1],[1,3],[3,1],[3,3],[2,2]]

Output: -1

Explanation:

<img alt="Example 2 diagram" src="https://assets.leetcode.com/uploads/2024/11/02/example2.png" style="width: 229px; height: 228px;" />

There is only one rectangle possible is with points <code>[1,1], [1,3], [3,1]</code> and <code>[3,3]</code> but <code>[2,2]</code> will always lie inside it. Hence, returning -1.
</div>

Example 3:

<div class="example-block">
Input: points = [[1,1],[1,3],[3,1],[3,3],[1,2],[3,2]]

Output: 2

Explanation:

<img alt="Example 3 diagram" src="https://assets.leetcode.com/uploads/2024/11/02/example3.png" style="width: 229px; height: 228px;" />

The maximum area rectangle is formed by the points <code>[1,3], [1,2], [3,2], [3,3]</code>, which has an area of 2. Additionally, the points <code>[1,1], [1,2], [3,1], [3,2]</code> also form a valid rectangle with the same area.
</div>

&nbsp;
Constraints:

<ul>
	<li><code>1 &lt;= points.length &lt;= 10</code></li>
	<li><code>points[i].length == 2</code></li>
	<li><code>0 &lt;= xi, yi &lt;= 100</code></li>
	<li>All the given points are unique.</li>
</ul>

maxRectangleArea

Maximum Area Rectangle With Point Constraints I

Minimum Area Rectangle

minimum-area-rectangle

最小面积矩形

Binary Indexed Tree

Segment Tree

Geometry

Array

Math

Enumeration

Sorting

给你一个数组 <code>points</code>，其中 <code>points[i] = [xi, yi]</code> 表示无限平面上一点的坐标。

你的任务是找出满足以下条件的矩形可能的&nbsp;最大&nbsp;面积：

<ul>
	<li>矩形的四个顶点必须是数组中的&nbsp;四个&nbsp;点。</li>
	<li>矩形的内部或边界上&nbsp;不能&nbsp;包含任何其他点。</li>
	<li>矩形的边与坐标轴&nbsp;平行&nbsp;。</li>
</ul>

返回可以获得的&nbsp;最大面积&nbsp;，如果无法形成这样的矩形，则返回 -1。

&nbsp;

示例 1：

<div class="example-block">
输入： points = [[1,1],[1,3],[3,1],[3,3]]

输出：4

解释：

<img alt="示例 1 图示" src="https://assets.leetcode.com/uploads/2024/11/02/example1.png" style="width: 229px; height: 228px;" />

我们可以用这 4 个点作为顶点构成一个矩形，并且矩形内部或边界上没有其他点。因此，最大面积为 4 。
</div>

示例 2：

<div class="example-block">
输入： points = [[1,1],[1,3],[3,1],[3,3],[2,2]]

输出：-1

解释：

<img alt="示例 2 图示" src="https://assets.leetcode.com/uploads/2024/11/02/example2.png" style="width: 229px; height: 228px;" />

唯一一组可能构成矩形的点为 <code>[1,1], [1,3], [3,1]</code> 和 <code>[3,3]</code>，但点 <code>[2,2]</code> 总是位于矩形内部。因此，返回 -1 。
</div>

示例 3：

<div class="example-block">
输入： points = [[1,1],[1,3],[3,1],[3,3],[1,2],[3,2]]

输出：2

解释：

<img alt="示例 3 图示" src="https://assets.leetcode.com/uploads/2024/11/02/example3.png" style="width: 229px; height: 228px;" />

点 <code>[1,3], [1,2], [3,2], [3,3]</code>&nbsp;可以构成面积最大的矩形，面积为 2。此外，点 <code>[1,1], [1,2], [3,1], [3,2]</code> 也可以构成一个符合题目要求的矩形，面积相同。
</div>

&nbsp;

提示：

<ul>
	<li><code>1 &lt;= points.length &lt;= 10</code></li>
	<li><code>points[i].length == 2</code></li>
	<li><code>0 &lt;= xi, yi &lt;= 100</code></li>
	<li>给定的所有点都是 唯一 的。</li>
</ul>