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++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
// 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_; }; |
请尊重作者的劳动成果,转载请注明出处!花花保留对文章/视频的所有权利。
如果您喜欢这篇文章/视频,欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Be First to Comment