0028 원 내 랜 덤 생 성 점

원 내 랜 덤 생 성 점
번호: 0028
시험 문제 출처: leetcode 나의 블 로그: Something
제목 설명
원 의 반지름 과 원심 의 x 과 y 좌 표를 정 하고 원 에서 균일 한 랜 덤 점 을 만 드 는 함수 randPoint 를 쓴다.
설명:

입력 값 과 출력 값 은 모두 부동 소수점

이 될 것 이다.

원 의 반지름 과 원심 의 x, y 좌 표 는 매개 변수 로 클래스 에 전달 하 는 구조 함수

원주 상의 점도 원 중

에 있다 고 생각한다.

randPoint 무 작위 점 을 포함 하 는 x 좌표 와 y 좌표 의 크기 가 2 인 배열

을 되 돌려 줍 니 다.
풀이 알고리즘
사고의 방향 을 풀다.
이 문 제 는 두 가지 풀이 방향 이 있 는데 첫 번 째 는 샘플링 을 거부 하 는 것 이다. 바로 무 작위 로 생 성 되 기 쉬 운 도형 을 선택 하 는 것 이다. 예 를 들 어 정사각형 을 선택 하여 변 의 길 이 를 반지름 으로 만 들 면 정사각형 에서 무 작위 로 점 을 만 든 다음 에 이 점 이 원 안에 있 는 지 판단 하면 된다.
정사각형 중 무 작위 생 성 점

double x = r * (double)rand() / RAND_MAX;  //  rand()        RAND_MAX，         0~1      
double y = r * (double)rand() / RNAD_MAX;

이 점 이 원 안에 있 는 지 아 닌 지 를 판단 하 다.

while(x * x + y * y > r * r)//        

또 다른 방법 은 극좌 표 의 사고방식 으로 원 안에서 무 작위 로 점 을 찍 는 것 이다.
여기 서 우 리 는 먼저 각도 theta 를 취하 고 반경 tmpR 을 취 하 는 방법 을 선택한다.
우선 각도 theta, 각도 360, 선 택 된 것 등 가능 한 것 을 먼저 취하 기 때문에 간단하게 랜 덤 수 를 취하 면 됩 니 다.

double theta = 360 * (double)rand() /　RAND_MAX;

그리고 반경 tmpR 을 선택 하면 여기에 구덩이 가 하나 있다.나 는 처음에 모든 반지름 도 가능 하 다 고 생각 했 지만 사실은 그렇지 않 았 다.수학의 공식 으로 알 수 있 듯 이 면적 은 8747 ° 2 * 8727 ° p i * 8727 ° x \ int 2 * pi * x * 8747 ° 2 * 8727 ° pi * 8727 ° x 이 고 확률 밀도 공식 을 구 할 수 있 으 면 f (x) = 2 * 8727 ° x f (x) = 2 * x f (x) = 2 * 8727 ° x x 이 며 여 기 는 pi \ pi pi 를 무시 합 니 다. 아무런 영향 이 없 기 때 문 입 니 다.
그 다음 에 알 수 있 듯 이 임의의 한 변 의 길이 에 대해 점 이 이 변 의 길 이 를 반지름 으로 하 는 원 안에 떨 어 질 확률 은 F (x) = x 2 F (x) = x ^ 2 F (x) = x2 이 고 이런 확률 은 균일 하 게 분포 되 어야 하기 때문에 모든 확률 이 하나의 반지름 에 대응 할 수 있 기 때문에 우 리 는

double tmpR = r * sqrt((double)rand() / RAND_MAX); //    sqrt       x2    

그리고 이 두 개의 양 으로 정확 한 결 과 를 구 할 수 있 습 니 다.
코드 구현

class Solution {
private:
	double r;
	double x;
	double y;
public:
    Solution(double radius, double x_center, double y_center) {
    	srand((unsigned) time(NULL));
    	r = radius;
    	x = x_center;
    	y = y_center;
    }
    
    vector<double> randPoint() {
    	double theta = 2 * M_PI * (double)rand() / RAND_MAX;
    	double tmpR = r * sqrt((double)rand() / RAND_MAX);
    	vector<double> result;
    	result.push_back(x + tmpR * cos(theta));
    	result.push_back(y + tmpR * sin(theta));
    	return result;
    }
};