Posts tagged as “geometry”

花花酱 LeetCode 882. Random Point in Non-overlapping Rectangles

By zxi on July 28, 2018

Problem

Given a list of non-overlapping axis-aligned rectangles rects, write a function pick which randomly and uniformily picks an integer point in the space covered by the rectangles.

Note:

An integer point is a point that has integer coordinates.
A point on the perimeter of a rectangle is included in the space covered by the rectangles.
ith rectangle = rects[i] = [x1,y1,x2,y2], where [x1, y1] are the integer coordinates of the bottom-left corner, and [x2, y2] are the integer coordinates of the top-right corner.
length and width of each rectangle does not exceed 2000.
1 <= rects.length <= 100
pick return a point as an array of integer coordinates [p_x, p_y]
pick is called at most 10000 times.

Example 1:

Input: 
["Solution","pick","pick","pick"]
[[[[1,1,5,5]]],[],[],[]]
Output: 
[null,[4,1],[4,1],[3,3]]

Example 2:

Input: 
["Solution","pick","pick","pick","pick","pick"]
[[[[-2,-2,-1,-1],[1,0,3,0]]],[],[],[],[],[]]
Output: 
[null,[-1,-2],[2,0],[-2,-1],[3,0],[-2,-2]]

Explanation of Input Syntax:

The input is two lists: the subroutines called and their arguments. Solution‘s constructor has one argument, the array of rectangles rects. pick has no arguments. Arguments are always wrapped with a list, even if there aren’t any.

Solution: Binary Search

Same as LeetCode 880. Random Pick with Weight

Use area of the rectangles as weights.

Time complexity: Init: O(n) Pick: O(logn)

Space complexity: O(n)

// Author: Huahua

// Running time: 92 ms

class Solution {

public:

Solution(vector<vector<int>> rects): rects_(std::move(rects)) {

sums_ = vector<int>(rects_.size());

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

sums_[i] = (rects_[i][2] - rects_[i][0] + 1) * (rects_[i][3] - rects_[i][1] + 1);

if (i > 0) sums_[i] += sums_[i - 1];

}

vector<int> pick() {

const int s = nextInt(sums_.back()) + 1;

int index = lower_bound(sums_.begin(), sums_.end(), s) - sums_.begin();

const auto& rect = rects_[index];

return {rect[0] + nextInt(rect[2] - rect[0] + 1),

rect[1] + nextInt(rect[3] - rect[1] + 1)};

}

private:

vector<int> sums_;

vector<vector<int>> rects_;

// Returns a random int in [0, n - 1]

int nextInt(int n) {

return rand() / static_cast<double>(RAND_MAX) * n;

}

};

Problem

Given the radius and x-y positions of the center of a circle, write a function randPoint which generates a uniform random point in the circle.

Note:

input and output values are in floating-point.
radius and x-y position of the center of the circle is passed into the class constructor.
a point on the circumference of the circle is considered to be in the circle.
randPoint returns a size 2 array containing x-position and y-position of the random point, in that order.

Example 1:

Input: 
["Solution","randPoint","randPoint","randPoint"]
[[1,0,0],[],[],[]]
Output: [null,[-0.72939,-0.65505],[-0.78502,-0.28626],[-0.83119,-0.19803]]

Example 2:

Input: 
["Solution","randPoint","randPoint","randPoint"]
[[10,5,-7.5],[],[],[]]
Output: [null,[11.52438,-8.33273],[2.46992,-16.21705],[11.13430,-12.42337]]

Explanation of Input Syntax:

The input is two lists: the subroutines called and their arguments. Solution‘s constructor has three arguments, the radius, x-position of the center, and y-position of the center of the circle. randPoint has no arguments. Arguments are always wrapped with a list, even if there aren’t any.

Solution: Polar Coordinate

uniform sample an angle a: [0, 2*Pi)

uniform sample a radius r: [0, 1)

Number of random points in a cycle should be proportional to the square of distance to the center.

e.g. there are 4 times of points with distance d than points with distance d/2.

Thus sqrt(r) is uniformly distributed.

r’ = sqrt(r),

C++

// Author: Huahua

// Running time: 116 ms

class Solution {

public:

Solution(double radius, double x_center, double y_center)

:r_(radius), x_(x_center), y_(y_center) {}

vector<double> randPoint() {

double a = rand() / static_cast<double>(RAND_MAX) * 2 * M_PI;

double r = sqrt(rand() / static_cast<double>(RAND_MAX)) * r_;

return {x_ + r * cos(a), y_ + r * sin(a)};

}

private:

double r_;

double x_;

double y_;

};

花花酱 LeetCode 836. Rectangle Overlap

By zxi on July 19, 2018

Problem

A rectangle is represented as a list [x1, y1, x2, y2], where (x1, y1) are the coordinates of its bottom-left corner, and (x2, y2) are the coordinates of its top-right corner.

Two rectangles overlap if the area of their intersection is positive. To be clear, two rectangles that only touch at the corner or edges do not overlap.

Given two (axis-aligned) rectangles, return whether they overlap.

Example 1:

Input: rec1 = [0,0,2,2], rec2 = [1,1,3,3]
Output: true

Example 2:

Input: rec1 = [0,0,1,1], rec2 = [1,0,2,1]
Output: false

Notes:

Both rectangles rec1 and rec2 are lists of 4 integers.
All coordinates in rectangles will be between -10^9 and 10^9.

Solution: Geometry

Time complexity: O(1)

Space complexity: O(1)

// Author: Huahua

// Running time: 0 ms

class Solution {

public:

bool isRectangleOverlap(vector<int>& rec1, vector<int>& rec2) {

return rec1[0] < rec2[2] && rec2[0] < rec1[2] &&

rec1[1] < rec2[3] && rec2[1] < rec1[3];

}

};

花花酱 LeetCode 452. Minimum Number of Arrows to Burst Balloons

By zxi on June 23, 2018

Problem

There are a number of spherical balloons spread in two-dimensional space. For each balloon, provided input is the start and end coordinates of the horizontal diameter. Since it’s horizontal, y-coordinates don’t matter and hence the x-coordinates of start and end of the diameter suffice. Start is always smaller than end. There will be at most 10⁴ balloons.

An arrow can be shot up exactly vertically from different points along the x-axis. A balloon with x_start and x_endbursts by an arrow shot at x if x_start ≤ x ≤ x_end. There is no limit to the number of arrows that can be shot. An arrow once shot keeps travelling up infinitely. The problem is to find the minimum number of arrows that must be shot to burst all balloons.

Example:

Input:
[[10,16], [2,8], [1,6], [7,12]]

Output:
2

Explanation:
One way is to shoot one arrow for example at x = 6 (bursting the balloons [2,8] and [1,6]) and another arrow at x = 11 (bursting the other two balloons).

Solution: Sweep Line

Time complexity: O(nlogn)

Space complexity: O(1)

C++

// Author: Huahua

// Running time: 82 ms

class Solution {

public:

int findMinArrowShots(vector<pair<int, int>>& points) {

if (points.empty()) return 0;

sort(points.begin(), points.end(),

[&](const pair<int,int>& a, const pair<int,int>& b){

return a.second < b.second;

});

int right = points.front().second;

int ans = 1;

for (const auto& point : points) {

if (point.first > right) {

right = point.second;

++ans;

}

return ans;

}

};

Problem

题目大意：给你一些点，求用这些点能够成的最大的三角形面积是多少？

https://leetcode.com/problems/largest-triangle-area/description/

You have a list of points in the plane. Return the area of the largest triangle that can be formed by any 3 of the points.

Example:
Input: points = [[0,0],[0,1],[1,0],[0,2],[2,0]]
Output: 2
Explanation: 
The five points are show in the figure below. The red triangle is the largest.

Notes:

3 <= points.length <= 50.
No points will be duplicated.
-50 <= points[i][j] <= 50.
Answers within 10^-6 of the true value will be accepted as correct.

Solution: Brute Force

Time complexity: O(n^3)

Space complexity: O(1)

// Author: Huahua

// Running time: 11 ms

class Solution {

public:

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

const int n = points.size();

double best = 0.0;

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

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

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

const double a = dist(points[i], points[j]);

const double b = dist(points[i], points[k]);

const double c = dist(points[j], points[k]);

const double s = (a + b + c) / 2;

const double area = sqrt(s * (s - a) * (s - b) * (s - c));

best = max(best, area);

}

return best;

}

private:

static inline double dist(const vector<int>& p1, const vector<int>& p2) {

return sqrt((p1[0] - p2[0]) * (p1[0] - p2[0]) + (p1[1] - p2[1]) * (p1[1] - p2[1]));

}

};

Posts tagged as “geometry”

花花酱 LeetCode 882. Random Point in Non-overlapping Rectangles

Problem

Solution: Binary Search

Related Problems

花花酱 LeetCode 883. Generate Random Point in a Circle

Problem

Solution: Polar Coordinate

C++

花花酱 LeetCode 836. Rectangle Overlap

Problem

Solution: Geometry

花花酱 LeetCode 452. Minimum Number of Arrows to Burst Balloons

Problem

Solution: Sweep Line

Related Problems

花花酱 LeetCode 812. Largest Triangle Area

Problem

Solution: Brute Force