Posts tagged as “geometry”

花花酱 LeetCode 1779. Find Nearest Point That Has the Same X or Y Coordinate

By zxi on March 6, 2021

You are given two integers, x and y, which represent your current location on a Cartesian grid: (x, y). You are also given an array points where each points[i] = [a_i, b_i] represents that a point exists at (a_i, b_i). A point is valid if it shares the same x-coordinate or the same y-coordinate as your location.

Return the index (0-indexed) of the valid point with the smallest Manhattan distance from your current location. If there are multiple, return the valid point with the smallest index. If there are no valid points, return -1.

The Manhattan distance between two points (x₁, y₁) and (x₂, y₂) is abs(x₁ - x₂) + abs(y₁ - y₂).

Example 1:

Input: x = 3, y = 4, points = [[1,2],[3,1],[2,4],[2,3],[4,4]]
Output: 2
Explanation: Of all the points, only [3,1], [2,4] and [4,4] are valid. Of the valid points, [2,4] and [4,4] have the smallest Manhattan distance from your current location, with a distance of 1. [2,4] has the smallest index, so return 2.

Example 2:

Input: x = 3, y = 4, points = [[3,4]]
Output: 0
Explanation: The answer is allowed to be on the same location as your current location.

Example 3:

Input: x = 3, y = 4, points = [[2,3]]
Output: -1
Explanation: There are no valid points.

Constraints:

1 <= points.length <= 10⁴
points[i].length == 2
1 <= x, y, a_i, b_i <= 10⁴

Solution: Brute Force

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

C++

// Author: Huahua

class Solution {

public:

int nearestValidPoint(int x, int y, vector<vector<int>>& points) {

int min_dist = INT_MAX;

int ans = -1;

for (int i = 0; i < points.size(); ++i) {

const int dx = abs(points[i][0] - x);

const int dy = abs(points[i][1] - y);

if (dx * dy == 0 && dx + dy < min_dist) {

min_dist = dx + dy;

ans = i;

}

return ans;

}

};

花花酱 LeetCode 1739. Building Boxes

By zxi on January 23, 2021

You have a cubic storeroom where the width, length, and height of the room are all equal to n units. You are asked to place n boxes in this room where each box is a cube of unit side length. There are however some rules to placing the boxes:

You can place the boxes anywhere on the floor.
If box x is placed on top of the box y, then each side of the four vertical sides of the box y must either be adjacent to another box or to a wall.

Given an integer n, return the minimum possible number of boxes touching the floor.

Example 1:

Input: n = 3
Output: 3
Explanation: The figure above is for the placement of the three boxes.
These boxes are placed in the corner of the room, where the corner is on the left side.

Example 2:

Input: n = 4
Output: 3
Explanation: The figure above is for the placement of the four boxes.
These boxes are placed in the corner of the room, where the corner is on the left side.

Example 3:

Input: n = 10
Output: 6
Explanation: The figure above is for the placement of the ten boxes.
These boxes are placed in the corner of the room, where the corner is on the back side.

Constraints:

1 <= n <= 10⁹

Solution: Geometry

Step 1: Build a largest pyramid that has less then n cubes, whose base area is d*(d+1) / 2
Step 2: Build a largest triangle with cubes left, whose base area is l, l*(l + 1) / 2 >= left

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

C++

// Author: Huahua

class Solution {

public:

int minimumBoxes(int n) {

int d = 0;

int l = 0;

while (n - (d + 1) * (d + 2) / 2 > 0) {

n -= (d + 1) * (d + 2) / 2;

++d;

}

while (n > 0) n -= ++l;

return d * (d + 1) / 2 + l;

}

};

花花酱 LeetCode 1515. Best Position for a Service Centre

By zxi on November 30, 2020

A delivery company wants to build a new service centre in a new city. The company knows the positions of all the customers in this city on a 2D-Map and wants to build the new centre in a position such that the sum of the euclidean distances to all customers is minimum.

Given an array positions where positions[i] = [x_i, y_i] is the position of the ith customer on the map, return the minimum sum of the euclidean distances to all customers.

In other words, you need to choose the position of the service centre [x_centre, y_centre] such that the following formula is minimized:

Answers within 10^-5 of the actual value will be accepted.

Example 1:

Input: positions = [[0,1],[1,0],[1,2],[2,1]]
Output: 4.00000
Explanation: As shown, you can see that choosing [x_centre, y_centre] = [1, 1] will make the distance to each customer = 1, the sum of all distances is 4 which is the minimum possible we can achieve.

Example 2:

Input: positions = [[1,1],[3,3]]
Output: 2.82843
Explanation: The minimum possible sum of distances = sqrt(2) + sqrt(2) = 2.82843

Example 3:

Input: positions = [[1,1]]
Output: 0.00000

Example 4:

Input: positions = [[1,1],[0,0],[2,0]]
Output: 2.73205
Explanation: At the first glance, you may think that locating the centre at [1, 0] will achieve the minimum sum, but locating it at [1, 0] will make the sum of distances = 3.
Try to locate the centre at [1.0, 0.5773502711] you will see that the sum of distances is 2.73205.
Be careful with the precision!

Example 5:

Input: positions = [[0,1],[3,2],[4,5],[7,6],[8,9],[11,1],[2,12]]
Output: 32.94036
Explanation: You can use [4.3460852395, 4.9813795505] as the position of the centre.

Constraints:

1 <= positions.length <= 50
positions[i].length == 2
0 <= positions[i][0], positions[i][1] <= 100

Solution: Weiszfeld’s algorithm

Use Weiszfeld’s algorithm to compute geometric median of the samples.

Time complexity: O(f(epsilon) * O)
Space complexity: O(1)

C++

template<typename T1, typename T2>

double dist(const vector<T1>& a, const vector<T2>& b) {

return sqrt((a[0] - b[0]) * (a[0] - b[0]) + (a[1] - b[1]) * (a[1] - b[1]));

};

class Solution {

public:

double getMinDistSum(vector<vector<int>>& positions) {

constexpr double kDelta = 1e-7;

constexpr double kEpsilon = 1e-15;

vector<double> c{-1, -1};

double ans = 0;

while (true) {

ans = 0;

double nx = 0, ny = 0;

double denominator = 0;

for (const auto& p : positions) {

double d = dist(c, p) + kEpsilon;

ans += d;

nx += p[0] / d;

ny += p[1] / d;

denominator += 1.0 / d;

}

vector<double> t{nx / denominator, ny / denominator};

if (dist(c, t) < kDelta) return ans;

c = t;

}

return -1;

}

};

花花酱 LeetCode 1637. Widest Vertical Area Between Two Points Containing No Points

By zxi on October 31, 2020

Given n points on a 2D plane where points[i] = [x_i, y_i], Return the widest vertical area between two points such that no points are inside the area.

A vertical area is an area of fixed-width extending infinitely along the y-axis (i.e., infinite height). The widest vertical area is the one with the maximum width.

Note that points on the edge of a vertical area are not considered included in the area.

Example 1:

Input: points = [[8,7],[9,9],[7,4],[9,7]]
Output: 1
Explanation: Both the red and the blue area are optimal.

Example 2:

Input: points = [[3,1],[9,0],[1,0],[1,4],[5,3],[8,8]]
Output: 3

Constraints:

n == points.length
2 <= n <= 10⁵
points[i].length == 2
0 <= x_i, y_i <= 10⁹

Solution: Sort by x coordinates

Time complexity: O(nlogn)
Space complexity: O(n)

C++

class Solution {

public:

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

sort(begin(points), end(points), [](const auto& p1, const auto& p2) {

return p1[0] != p2[0] ? p1[0] < p2[0] : p1[1] < p2[1];

});

int ans = 0;

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

ans = max(ans, points[i][0] - points[i - 1][0]);

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_;

};