Posts tagged as “rectangle”

花花酱 LeetCode 1401. Circle and Rectangle Overlapping

By zxi on April 4, 2020

Given a circle represented as (radius, x_center, y_center) and an axis-aligned rectangle represented as (x1, y1, x2, y2), where (x1, y1) are the coordinates of the bottom-left corner, and (x2, y2) are the coordinates of the top-right corner of the rectangle.

Return True if the circle and rectangle are overlapped otherwise return False.

In other words, check if there are any point (xi, yi) such that belongs to the circle and the rectangle at the same time.

Example 1:

Input: radius = 1, x_center = 0, y_center = 0, x1 = 1, y1 = -1, x2 = 3, y2 = 1
Output: true
Explanation: Circle and rectangle share the point (1,0)

Example 2:

Input: radius = 1, x_center = 0, y_center = 0, x1 = -1, y1 = 0, x2 = 0, y2 = 1
Output: true

Example 3:

Input: radius = 1, x_center = 1, y_center = 1, x1 = -3, y1 = -3, x2 = 3, y2 = 3
Output: true

Example 4:

Input: radius = 1, x_center = 1, y_center = 1, x1 = 1, y1 = -3, x2 = 2, y2 = -1
Output: false

Constraints:

1 <= radius <= 2000
-10^4 <= x_center, y_center, x1, y1, x2, y2 <= 10^4
x1 < x2
y1 < y2

Solution: Geometry

Find the shortest distance from the center to the rectangle, return dist <= radius.

Time complexity: O(1)
Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

bool checkOverlap(int radius, int x_center, int y_center, int x1, int y1, int x2, int y2) {

int dx = x_center - max(x1, min(x2, x_center));

int dy = y_center - max(y1, min(y2, y_center));

return dx * dx + dy * dy <= radius * radius;

}

};

花花酱 LeetCode 85. Maximal Rectangle

By zxi on January 26, 2019

Given a 2D binary matrix filled with 0’s and 1’s, find the largest rectangle containing only 1’s and return its area.

Example:

Input:
[
  ["1","0","1","0","0"],
  ["1","0","1","1","1"],
  ["1","1","1","1","1"],
  ["1","0","0","1","0"]
]
Output: 6

Solution: DP

Time complexity: O(m^2*n)
Space complexity: O(mn)

dp[i][j] := max length of all 1 sequence ends with col j, at the i-th row.
transition:
dp[i][j] = 0 if matrix[i][j] == ‘0’
= dp[i][j-1] + 1 if matrix[i][j] == ‘1’

C++

class Solution {

public:

int maximalRectangle(vector<vector<char> > &matrix) {

int r = matrix.size();

if (r == 0) return 0;

int c = matrix[0].size();

// dp[i][j] := max len of all 1s ends with col j at row i.

vector<vector<int>> dp(r, vector<int>(c));

for (int i = 0; i < r; ++i)

for (int j = 0; j < c; ++j)

dp[i][j] = (matrix[i][j] == '1') ? (j == 0 ? 1 : dp[i][j - 1] + 1) : 0;

int ans = 0;

for (int i = 0; i < r; ++i)

for (int j = 0; j < c; ++j) {

int len = INT_MAX;

for (int k = i; k < r; k++) {

len = min(len, dp[k][j]);

if (len == 0) break;

ans = max(len * (k - i + 1), ans);

}

return ans;

}

};

花花酱 LeetCode 963. Minimum Area Rectangle II

By zxi on December 26, 2018

Given a set of points in the xy-plane, determine the minimum area of any rectangle formed from these points, with sides not necessarily parallel to the x and y axes.

If there isn’t any rectangle, return 0.

Example 1:

Input: [[1,2],[2,1],[1,0],[0,1]]
Output: 2.00000
Explanation: The minimum area rectangle occurs at [1,2],[2,1],[1,0],[0,1], with an area of 2.

Example 2:

Input: [[0,1],[2,1],[1,1],[1,0],[2,0]]
Output: 1.00000
Explanation: The minimum area rectangle occurs at [1,0],[1,1],[2,1],[2,0], with an area of 1.

Example 3:

Input: [[0,3],[1,2],[3,1],[1,3],[2,1]]
Output: 0
Explanation: There is no possible rectangle to form from these points.

Example 4:

Input: [[3,1],[1,1],[0,1],[2,1],[3,3],[3,2],[0,2],[2,3]]
Output: 2.00000
Explanation: The minimum area rectangle occurs at [2,1],[2,3],[3,3],[3,1], with an area of 2.

Note:

1 <= points.length <= 50
0 <= points[i][0] <= 40000
0 <= points[i][1] <= 40000
All points are distinct.
Answers within 10^-5 of the actual value will be accepted as correct.

Solution: HashTable

Iterate all possible triangles and check the opposite points that creating a quadrilateral.

Time complexity: O(n^3)
Space complexity: O(n)

C++

class Solution {

public:

double minAreaFreeRect(vector<vector<int>>& points) {

constexpr double INF_AREA = 1e100;

const auto n = points.size();

unordered_set<int> s;

for (const auto& p : points)

s.insert(p[0] << 16 | p[1]);

double min_area = INF_AREA;

for (int i = 0; i < n; ++i)

for (int j = 0; j < n; ++j) {

if (i == j) continue;

for (int k = 0; k < n; ++k) {

if (i == k || j == k) continue;

const auto& p1 = points[i];

const auto& p2 = points[j];

const auto& p3 = points[k];

int dot = (p2[0] - p1[0]) * (p3[0] - p1[0]) +

(p2[1] - p1[1]) * (p3[1] - p1[1]);

if (dot != 0) continue;

int p4_x = p2[0] + p3[0] - p1[0];

int p4_y = p2[1] + p3[1] - p1[1];

if (!s.count(p4_x << 16 | p4_y)) continue;

double a = pow(p2[0] - p1[0], 2) + pow(p2[1] - p1[1], 2);

double b = pow(p3[0] - p1[0], 2) + pow(p3[1] - p1[1], 2);

double area = a * b;

min_area = min(min_area, area);

}

return min_area < INF_AREA ? sqrt(min_area) : 0;

}

};

花花酱 LeetCode 939. Minimum Area Rectangle

By zxi on November 11, 2018

Problem

Given a set of points in the xy-plane, determine the minimum area of a rectangle formed from these points, with sides parallel to the x and y axes.

If there isn’t any rectangle, return 0.

Example 1:

Input: [[1,1],[1,3],[3,1],[3,3],[2,2]]
Output: 4

Example 2:

Input: [[1,1],[1,3],[3,1],[3,3],[4,1],[4,3]]
Output: 2

Note:

1 <= points.length <= 500
0 <= points[i][0] <= 40000
0 <= points[i][1] <= 40000
All points are distinct.

Solution 1: HashTable + Brute Force

Try all pairs of points to form a diagonal and see whether pointers of another diagonal exist or not.

Assume two points are (x0, y0), (x1, y1) x0 != x1 and y0 != y1. The other two points will be (x0, y1), (x1, y0)

Time complexity: O(n^2)

Space complexity: O(n)

C++

// Author: Huahua, running time: 96 ms

class Solution {

public:

int minAreaRect(vector<vector<int>>& points) {

unordered_map<int, unordered_set<int>> s;

for (const auto& point : points)

s[point[0]].insert(point[1]);

const int n = points.size();

int min_area = INT_MAX;

for (int i = 0; i < n; ++i)

for (int j = i + 1; j < n; ++j) {

int x0 = points[i][0];

int y0 = points[i][1];

int x1 = points[j][0];

int y1 = points[j][1];

if (x0 == x1 || y0 == y1) continue;

int area = abs(x0 - x1) * abs(y0 - y1);

if (area > min_area) continue;

if (!s[x1].count(y0) || !s[x0].count(y1)) continue;

min_area = area;

}

return min_area == INT_MAX ? 0 : min_area;

}

};

C++ / 1D hashtable

// Author: Huahua, 68 ms

class Solution {

public:

int minAreaRect(vector<vector<int>>& points) {

unordered_set<int> s;

for (const auto& point : points)

s.insert((point[0] << 16) | point[1]);

const int n = points.size();

int min_area = INT_MAX;

for (int i = 0; i < n; ++i)

for (int j = i + 1; j < n; ++j) {

int x0 = points[i][0];

int y0 = points[i][1];

int x1 = points[j][0];

int y1 = points[j][1];

if (x0 == x1 || y0 == y1) continue;

int area = abs(x0 - x1) * abs(y0 - y1);

if (area > min_area) continue;

int p0 = (x1 << 16) | y0;

int p1 = (x0 << 16) | y1;

if (!s.count(p0) || !s.count(p1)) continue;

min_area = area;

}

return min_area == INT_MAX ? 0 : min_area;

}

};

花花酱 LeetCode 223. Rectangle Area

By zxi on September 19, 2018

Problem

Find the total area covered by two rectilinear rectangles in a 2D plane.

Each rectangle is defined by its bottom left corner and top right corner as shown in the figure.

Example:

Input: A = -3, B = 0, C = 3, D = 4, E = 0, F = -1, G = 9, H = 2
Output: 45

Note:

Assume that the total area is never beyond the maximum possible value of int.

Solution:

area1 + area2 – overlapped area

Time complexity: O(1)

Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

int computeArea(int A, int B, int C, int D, int E, int F, int G, int H) {

int area1 = (C - A) * (D - B);

int area2 = (G - E) * (H - F);

int x1 = max(A, E);

int x2 = max(x1, min(C, G));

int y1 = max(B, F);

int y2 = max(y1, min(D, H));

return area1 + area2 - (x2 - x1) * (y2 - y1);

}

};

Java

// Author: Huahua

class Solution {

public int computeArea(int A, int B, int C, int D, int E, int F, int G, int H) {

int area1 = (C - A) * (D - B);

int area2 = (G - E) * (H - F);

int x1 = Math.max(A, E);

int x2 = Math.max(x1, Math.min(C, G));

int y1 = Math.max(B, F);

int y2 = Math.max(y1, Math.min(D, H));

return area1 + area2 - (x2 - x1) * (y2 - y1);

}

Python3

# Author: Huahua

class Solution:

def computeArea(self, A, B, C, D, E, F, G, H):

area1 = (C - A) * (D - B);

area2 = (G - E) * (H - F);

x1 = max(A, E);

x2 = max(x1, min(C, G));

y1 = max(B, F);

y2 = max(y1, min(D, H));

return area1 + area2 - (x2 - x1) * (y2 - y1)