Posts published in “Geometry”

花花酱 LeetCode 1620. Coordinate With Maximum Network Quality

By zxi on October 17, 2020

You are given an array of network towers towers and an integer radius, where towers[i] = [x_i, y_i, q_i] denotes the i^th network tower with location (x_i, y_i) and quality factor q_i. All the coordinates are integral coordinates on the X-Y plane, and the distance between two coordinates is the Euclidean distance.

The integer radius denotes the maximum distance in which the tower is reachable. The tower is reachable if the distance is less than or equal to radius. Outside that distance, the signal becomes garbled, and the tower is not reachable.

The signal quality of the i^th tower at a coordinate (x, y) is calculated with the formula ⌊q_i / (1 + d)⌋, where d is the distance between the tower and the coordinate. The network quality at a coordinate is the sum of the signal qualities from all the reachable towers.

Return the integral coordinate where the network quality is maximum. If there are multiple coordinates with the same network quality, return the lexicographically minimum coordinate.

Note:

A coordinate (x1, y1) is lexicographically smaller than (x2, y2) if either x1 < x2 or x1 == x2 and y1 < y2.
⌊val⌋ is the greatest integer less than or equal to val (the floor function).

Example 1:

Input: towers = [[1,2,5],[2,1,7],[3,1,9]], radius = 2
Output: [2,1]
Explanation: 
At coordinate (2, 1) the total quality is 13
- Quality of 7 from (2, 1) results in ⌊7 / (1 + sqrt(0)⌋ = ⌊7⌋ = 7
- Quality of 5 from (1, 2) results in ⌊5 / (1 + sqrt(2)⌋ = ⌊2.07⌋ = 2
- Quality of 9 from (3, 1) results in ⌊9 / (1 + sqrt(1)⌋ = ⌊4.5⌋ = 4
No other coordinate has higher quality.

Example 2:

Input: towers = [[23,11,21]], radius = 9
Output: [23,11]

Example 3:

Input: towers = [[1,2,13],[2,1,7],[0,1,9]], radius = 2
Output: [1,2]

Example 4:

Input: towers = [[2,1,9],[0,1,9]], radius = 2
Output: [0,1]
Explanation: Both (0, 1) and (2, 1) are optimal in terms of quality but (0, 1) is lexicograpically minimal.

Constraints:

1 <= towers.length <= 50
towers[i].length == 3
0 <= x_i, y_i, q_i <= 50
1 <= radius <= 50

Solution: Brute Force

Try all possible coordinates from (0, 0) to (50, 50).

Time complexity: O(|X|*|Y|*t)
Space complexity: O(1)

C++

class Solution {

public:

vector<int> bestCoordinate(vector<vector<int>>& towers, int radius) {

constexpr int n = 50;

vector<int> ans;

int max_q = 0;

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

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

int q = 0;

for (const auto& tower : towers) {

const int tx = tower[0], ty = tower[1];

const float d = sqrt((x - tx) * (x - tx) + (y - ty) * (y - ty));

if (d > radius) continue;

q += floor(tower[2] / (1 + d));

}

if (q > max_q) {

max_q = q;

ans = {x, y};

}

return ans;

}

};

花花酱 LeetCode 1476. Subrectangle Queries

By zxi on June 13, 2020

Implement the class SubrectangleQueries which receives a rows x cols rectangle as a matrix of integers in the constructor and supports two methods:

1. updateSubrectangle(int row1, int col1, int row2, int col2, int newValue)

Updates all values with newValue in the subrectangle whose upper left coordinate is (row1,col1) and bottom right coordinate is (row2,col2).

2. getValue(int row, int col)

Returns the current value of the coordinate (row,col) from the rectangle.

Example 1:

Input
["SubrectangleQueries","getValue","updateSubrectangle","getValue","getValue","updateSubrectangle","getValue","getValue"]
[[[[1,2,1],[4,3,4],[3,2,1],[1,1,1]]],[0,2],[0,0,3,2,5],[0,2],[3,1],[3,0,3,2,10],[3,1],[0,2]]
Output

[null,1,null,5,5,null,10,5]

Explanation SubrectangleQueries subrectangleQueries = new SubrectangleQueries([[1,2,1],[4,3,4],[3,2,1],[1,1,1]]); // The initial rectangle (4×3) looks like: // 1 2 1 // 4 3 4 // 3 2 1 // 1 1 1 subrectangleQueries.getValue(0, 2); // return 1 subrectangleQueries.updateSubrectangle(0, 0, 3, 2, 5); // After this update the rectangle looks like: // 5 5 5 // 5 5 5 // 5 5 5 // 5 5 5 subrectangleQueries.getValue(0, 2); // return 5 subrectangleQueries.getValue(3, 1); // return 5 subrectangleQueries.updateSubrectangle(3, 0, 3, 2, 10); // After this update the rectangle looks like: // 5 5 5 // 5 5 5 // 5 5 5 // 10 10 10 subrectangleQueries.getValue(3, 1); // return 10 subrectangleQueries.getValue(0, 2); // return 5

Example 2:

Input
["SubrectangleQueries","getValue","updateSubrectangle","getValue","getValue","updateSubrectangle","getValue"]
[[[[1,1,1],[2,2,2],[3,3,3]]],[0,0],[0,0,2,2,100],[0,0],[2,2],[1,1,2,2,20],[2,2]]
Output

[null,1,null,100,100,null,20]

Explanation SubrectangleQueries subrectangleQueries = new SubrectangleQueries([[1,1,1],[2,2,2],[3,3,3]]); subrectangleQueries.getValue(0, 0); // return 1 subrectangleQueries.updateSubrectangle(0, 0, 2, 2, 100); subrectangleQueries.getValue(0, 0); // return 100 subrectangleQueries.getValue(2, 2); // return 100 subrectangleQueries.updateSubrectangle(1, 1, 2, 2, 20); subrectangleQueries.getValue(2, 2); // return 20

Constraints:

There will be at most 500 operations considering both methods: updateSubrectangle and getValue.
1 <= rows, cols <= 100
rows == rectangle.length
cols == rectangle[i].length
0 <= row1 <= row2 < rows
0 <= col1 <= col2 < cols
1 <= newValue, rectangle[i][j] <= 10^9
0 <= row < rows
0 <= col < cols

Solution 1: Simulation

Update the matrix values.

Time complexity:
Update: O(m*n), where m*n is the area of the sub-rectangle.
Query: O(1)

Space complexity: O(rows*cols)

C++

// Author: Huahua

class SubrectangleQueries {

public:

SubrectangleQueries(vector<vector<int>>& rectangle):

m_(rectangle) {}

void updateSubrectangle(int row1, int col1, int row2, int col2, int newValue) {

for (int i = row1; i <= row2; ++i)

for (int j = col1; j <= col2; ++j)

m_[i][j] = newValue;

}

int getValue(int row, int col) {

return m_[row][col];

}

private:

vector<vector<int>> m_;

};

Solution 2: Geometry

For each update remember the region and value.

For each query, find the newest updates that covers the query point. If not found, return the original value in the matrix.

Time complexity:
Update: O(1)
Query: O(|U|), where |U| is the number of updates so far.

Space complexity: O(|U|)

C++

// Author: Huahua

class SubrectangleQueries {

public:

SubrectangleQueries(vector<vector<int>>& rectangle):

m_(rectangle) {}

void updateSubrectangle(int row1, int col1, int row2, int col2, int newValue) {

updates_.push_front({row1, col1, row2, col2, newValue});

}

int getValue(int row, int col) {

for (const auto& u : updates_)

if (row >= u[0] && row <= u[2] && col >= u[1] && col <= u[3])

return u[4];

return m_[row][col];

}

private:

const vector<vector<int>>& m_;

deque<vector<int>> updates_;

};

花花酱 LeetCode 1465. Maximum Area of a Piece of Cake After Horizontal and Vertical Cuts

By zxi on May 31, 2020

Given a rectangular cake with height h and width w, and two arrays of integers horizontalCuts and verticalCuts where horizontalCuts[i] is the distance from the top of the rectangular cake to the ith horizontal cut and similarly, verticalCuts[j] is the distance from the left of the rectangular cake to the jth vertical cut.

Return the maximum area of a piece of cake after you cut at each horizontal and vertical position provided in the arrays horizontalCuts and verticalCuts. Since the answer can be a huge number, return this modulo 10^9 + 7.

Example 1:

Input: h = 5, w = 4, horizontalCuts = [1,2,4], verticalCuts = [1,3]
Output: 4 
Explanation: The figure above represents the given rectangular cake. Red lines are the horizontal and vertical cuts. After you cut the cake, the green piece of cake has the maximum area.

Example 2:

Input: h = 5, w = 4, horizontalCuts = [3,1], verticalCuts = [1]
Output: 6
Explanation: The figure above represents the given rectangular cake. Red lines are the horizontal and vertical cuts. After you cut the cake, the green and yellow pieces of cake have the maximum area.

Example 3:

Input: h = 5, w = 4, horizontalCuts = [3], verticalCuts = [3]
Output: 9

Constraints:

2 <= h, w <= 10^9
1 <= horizontalCuts.length < min(h, 10^5)
1 <= verticalCuts.length < min(w, 10^5)
1 <= horizontalCuts[i] < h
1 <= verticalCuts[i] < w
It is guaranteed that all elements in horizontalCuts are distinct.
It is guaranteed that all elements in verticalCuts are distinct.

Solution: Geometry

Find the max gap between vertical cuts mx and max gap between horizontal cuts my. ans = mx * my

Time complexity: O(nlogn)
Space complexity: O(1) if sort in place otherweise O(n)

C++

// Author: Huahua

class Solution {

public:

int maxArea(int h, int w, vector<int>& horizontalCuts, vector<int>& verticalCuts) {

constexpr int kMod = 1e9 + 7;

sort(begin(verticalCuts), end(verticalCuts));

sort(begin(horizontalCuts), end(horizontalCuts));

int mx = max(verticalCuts[0], w - verticalCuts.back());

int my = max(horizontalCuts[0], h - horizontalCuts.back());

for (int i = 1; i < verticalCuts.size(); ++i)

mx = max(mx, verticalCuts[i] - verticalCuts[i - 1]);

for (int i = 1; i < horizontalCuts.size(); ++i)

my = max(my, horizontalCuts[i] - horizontalCuts[i - 1]);

return static_cast<long>(mx) * my % kMod;

}

};

花花酱 LeetCode 1453. Maximum Number of Darts Inside of a Circular Dartboard

By zxi on May 16, 2020

You have a very large square wall and a circular dartboard placed on the wall. You have been challenged to throw darts into the board blindfolded. Darts thrown at the wall are represented as an array of points on a 2D plane.

Return the maximum number of points that are within or lie on any circular dartboard of radius r.

Example 1:

Input: points = [[-2,0],[2,0],[0,2],[0,-2]], r = 2
Output: 4
Explanation: Circle dartboard with center in (0,0) and radius = 2 contain all points.

Example 2:

Input: points = [[-3,0],[3,0],[2,6],[5,4],[0,9],[7,8]], r = 5
Output: 5
Explanation: Circle dartboard with center in (0,4) and radius = 5 contain all points except the point (7,8).

Example 3:

Input: points = [[-2,0],[2,0],[0,2],[0,-2]], r = 1
Output: 1

Example 4:

Input: points = [[1,2],[3,5],[1,-1],[2,3],[4,1],[1,3]], r = 2
Output: 4

Constraints:

1 <= points.length <= 100
points[i].length == 2
-10^4 <= points[i][0], points[i][1] <= 10^4
1 <= r <= 5000

Solution 1: Angular Sweep

See for more details: https://www.geeksforgeeks.org/angular-sweep-maximum-points-can-enclosed-circle-given-radius/

Time complexity: O(n^2*logn)
Space complexity: O(n^2)

C++

// Author: Huahua

// Python-Like enumerate() In C++17

// http://reedbeta.com/blog/python-like-enumerate-in-cpp17/

template <typename T,

typename TIter = decltype(std::begin(std::declval<T>())),

typename = decltype(std::end(std::declval<T>()))>

constexpr auto enumerate(T && iterable) {

struct iterator {

size_t i;

TIter iter;

bool operator != (const iterator & other) const { return iter != other.iter; }

void operator ++ () { ++i; ++iter; }

auto operator * () const { return std::tie(i, *iter); }

};

struct iterable_wrapper {

T iterable;

auto begin() { return iterator{ 0, std::begin(iterable) }; }

auto end() { return iterator{ 0, std::end(iterable) }; }

};

return iterable_wrapper{ std::forward<T>(iterable) };

}

class Solution {

public:

int numPoints(vector<vector<int>>& points, int r) {

const int n = points.size();

vector<vector<double>> d(n, vector<double>(n));

for (const auto& [i, pi] : enumerate(points))

for (const auto& [j, pj] : enumerate(points))

d[i][j] = d[j][i] = sqrt((pi[0] - pj[0]) * (pi[0] - pj[0])

+ (pi[1] - pj[1]) * (pi[1] - pj[1]));

int ans = 1;

for (const auto& [i, pi] : enumerate(points)) {

vector<pair<double, int>> angles; // {angle, event_type}

for (const auto& [j, pj] : enumerate(points)) {

if (i != j && d[i][j] <= 2 * r) {

const double a = atan2(pj[1] - pi[1], pj[0] - pi[0]);

const double b = acos(d[i][j] / (2 * r));

angles.emplace_back(a - b, -1); // entering

angles.emplace_back(a + b, 1); // exiting

}

// If angles are the same, entering points go first.

sort(begin(angles), end(angles));

int pts = 1;

for (const auto& [_, event] : angles)

ans = max(ans, pts -= event);

}

return ans;

}

};

花花酱 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;

}

};