478. 在圆内随机生成点

难度中等37

给定圆的半径和圆心的 x、y 坐标，写一个在圆中产生均匀随机点的函数 randPoint 。

说明:

  1. 输入值和输出值都将是浮点数。
  2. 圆的半径和圆心的 x、y 坐标将作为参数传递给类的构造函数。
  3. 圆周上的点也认为是在圆中。
  4. randPoint 返回一个包含随机点的x坐标和y坐标的大小为2的数组。

示例 1：

1
2
3
4
输入: 
["Solution","randPoint","randPoint","randPoint"]
[[1,0,0],[],[],[]]
输出: [null,[-0.72939,-0.65505],[-0.78502,-0.28626],[-0.83119,-0.19803]]

示例 2：

1
2
3
4
输入: 
["Solution","randPoint","randPoint","randPoint"]
[[10,5,-7.5],[],[],[]]
输出: [null,[11.52438,-8.33273],[2.46992,-16.21705],[11.13430,-12.42337]]

输入语法说明：

输入是两个列表：调用成员函数名和调用的参数。Solution 的构造函数有三个参数，圆的半径、圆心的 x 坐标、圆心的 y 坐标。randPoint 没有参数。输入参数是一个列表，即使参数为空，也会输入一个 [] 空列表。

C++11新特性,随机数库,不香嘛？

https://blog.csdn.net/qq_23225317/article/details/79787543

基本语法:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include<iostream>
#include<cstdlib>
#include<ctime>
std::random_device rd;
std::default_random_engine e(rd());
//e.seed(time(0));
//随机整数
std::uniform_int_distribution<unsigned> u(0, 9);
//随机实数
std::uniform_real_distribution<double> u2(0, 1);
for(size_t i = 0; i < 10; i++)
    std::cout<<u2(e)<<'\t';
//正态分布
std::cout<<"test normal distribution:\n";
e.seed(time(0));
std::normal_distribution<> n(4, 1.5);
std::vector<unsigned> vals(9);
for(size_t i = 0; i < 250; i++)
{
    unsigned v = lround(n(e));
    if(v < vals.size()) vals[v]++;
}

for(size_t i = 0; i < vals.size(); i++)
{
    std::cout<<i<<": "<<std::string(vals[i], '*')<<std::endl;
}
std::cout<<"test normal distribution done.\n"<<std::endl;
//伯努利分布
std::cout<<"test bernoulli distribution:\n";
e.seed(time(0));
std::bernoulli_distribution b(0.7);
std::vector<unsigned> bers(2);
for(size_t i = 0; i < 200; i++)
{
    if(b(e)) bers[1]++;
    else bers[0]++;
}
std::cout<<"True: "<<bers[1]<<std::endl;
std::cout<<"False: "<<bers[0]<<std::endl;
std::cout<<"test bernoulli distribution done.\n";

某一个题解:

相信大部分人都没有看懂，我就来通俗地解释一下吧。

确定圆内一点，需要有相对于圆心的距离r，以及相对于圆心的角度angle。

一开始的想法，我们在[0, radius]中等概率取r，在[0, 2π)中等概率取angle即可实现圆内的随机分布。

事实上，这是不对的。

在[0, 2π)中等概率取angle，相对于把一个圆分成了无数个扇形，点落在每个扇形上的概率均相等。

假设某个扇形的圆心角是theta，那么该扇形的面积是0.5 theta radius ^ 2，分布在该扇形区域上的概率是theta / 2π，只要每个扇形的圆心角相等，扇形面积就是相等的，点在扇形中也是等概率的。

在[0, radius]中等概率取r，相当于把一个圆分成了无数个环形，点落在每个环形上的概率均相等。

假设某个环形的内径是r1，外径是r2，那么该环形的面积是π * (r2 ^ 2 - r1 ^ 2)。可见每个环形的面积是不一样的，显然每个环形上的点密度是不一样的。这样做会造成靠近圆心的点分布比较密集，远离圆心的点分布比较稀疏。

那么，如何取r使得点落在圆内任意区域的概率均相等呢？这样做显然会使得落在每个环形上的概率均不同，且环形面积较大的概率高，环形面积较小的概率小。

根据环形面积的计算公式：π * (r2 ^ 2 - r1 ^ 2)，落在该环形面积上的概率应为(r2 ^ 2 - r1 ^ 2) / (radius ^ 2)。

在[0, radius]中如何分布概率密度函数f(x)，可以使得f(x)其在[r1, r2]上的积分值为(r2 ^ 2 - r1 ^ 2) / (radius ^ 2)呢？

取f(x) = 2x / (radius ^ 2)可以满足上述条件，即半径r在[0, radius]上的概率密度函数应为f(x) = 2x / (radius ^ 2)，故只需要在[0, radius ^ 2]范围内等概率取r ^ 2，再开根号即得r值。（求一下导数即可，x ^ 2的导数是2x）

时间复杂度是和空间复杂度均是O(1)。

image-20200925171304597

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
class Solution {
private:
    double radius;
    double x_center,y_center;
    double _2pi;
public:
//极坐标:x=rcos(\theta),y=rsin(\theta)
    Solution(double radius, double x_center, double y_center) {
        this->radius=radius;
        this->x_center=x_center;
        this->y_center=y_center;
        this->_2pi=acos(-1)*2;
    }
    
    vector<double> randPoint() {
        vector<double>result;
        if(radius>0){
            random_device rd;
            default_random_engine e(rd());
            uniform_real_distribution<double>u1(0,radius*radius);
            uniform_real_distribution<double>u2(0,_2pi);//acos(-1)*2=2\pi

            double r=sqrt(u1(e));
            double theta=u2(e);

            double x=x_center+r*cos(theta);
            double y=y_center+r*sin(theta);
            result.push_back(x);
            result.push_back(y);
        }
        return result;
    }
};

/**
 * Your Solution object will be instantiated and called as such:
 * Solution* obj = new Solution(radius, x_center, y_center);
 * vector<double> param_1 = obj->randPoint();
 */