478. Generate Random Point in a Circle

leetcode medium

#array#csharp#design#leetcode#math#medium

Task

Дан радиус и положение центра окружности, реализуйте функцию randPoint, которая генерирует равномерно случайную точку внутри окружности.

Реализуйте класс Solution:

- Solution(double radius, double x_center, double y_center) инициализирует объект с радиусом окружности radius и положением центра (x_center, y_center).

- randPoint() возвращает случайную точку внутри окружности. Точка на окружности считается находящейся внутри окружности. Ответ возвращается в виде массива [x, y].

Пример:

Input

["Solution", "randPoint", "randPoint", "randPoint"]

[[1.0, 0.0, 0.0], [], [], []]

Output

[null, [-0.02493, -0.38077], [0.82314, 0.38945], [0.36572, 0.17248]]

Explanation

Solution solution = new Solution(1.0, 0.0, 0.0);

solution.randPoint(); // return [-0.02493, -0.38077]

solution.randPoint(); // return [0.82314, 0.38945]

solution.randPoint(); // return [0.36572, 0.17248]

C# solution

matched/original

using System;
public class Solution {
    double rad, xc, yc;
    public Solution(double radius, double x_center, double y_center) {
        rad = radius;
        xc = x_center;
        yc = y_center;
    }
    public double[] RandPoint() {
        double x0 = xc - rad;
        double y0 = yc - rad;
        while (true) {
            double xg = x0 + new Random().NextDouble() * rad * 2;
            double yg = y0 + new Random().NextDouble() * rad * 2;
            if (Math.Sqrt(Math.Pow(xg - xc, 2) + Math.Pow(yg - yc, 2)) <= rad) {
                return new double[] { xg, yg };
            }
        }
    }
}

C++ solution

auto-draft, review before submit

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    double rad, xc, yc;
    public Solution(double radius, double x_center, double y_center) {
        rad = radius;
        xc = x_center;
        yc = y_center;
    }
    public double[] RandPoint() {
        double x0 = xc - rad;
        double y0 = yc - rad;
        while (true) {
            double xg = x0 + new Random().NextDouble() * rad * 2;
            double yg = y0 + new Random().NextDouble() * rad * 2;
            if (Math.Sqrt(Math.Pow(xg - xc, 2) + Math.Pow(yg - yc, 2)) <= rad) {
                return new double[] { xg, yg };
            }
        }
    }
}

Java solution

matched/original

class Solution {
    double rad, xc, yc;

    public Solution(double radius, double x_center, double y_center) {
        rad = radius;
        xc = x_center;
        yc = y_center;
    }

    public double[] randPoint() {
        double x0 = xc - rad;
        double y0 = yc - rad;

        while (true) {
            double xg = x0 + Math.random() * rad * 2;
            double yg = y0 + Math.random() * rad * 2;
            if (Math.sqrt(Math.pow((xg - xc), 2) + Math.pow((yg - yc), 2)) <= rad) {
                return new double[]{xg, yg};
            }
        }
    }
}

JavaScript solution

matched/original

class Solution {
    constructor(radius, x_center, y_center) {
        this.rad = radius;
        this.xc = x_center;
        this.yc = y_center;
    }

    randPoint() {
        const x0 = this.xc - this.rad;
        const y0 = this.yc - this.rad;

        while (true) {
            const xg = x0 + Math.random() * this.rad * 2;
            const yg = y0 + Math.random() * this.rad * 2;
            if (Math.sqrt(Math.pow(xg - this.xc, 2) + Math.pow(yg - this.yc, 2)) <= this.rad) {
                return [xg, yg];
            }
        }
    }
}

Python solution

matched/original

import random
import math

class Solution:

    def __init__(self, radius: float, x_center: float, y_center: float):
        self.rad = radius
        self.xc = x_center
        self.yc = y_center

    def randPoint(self) -> List[float]:
        x0, y0 = self.xc - self.rad, self.yc - self.rad

        while True:
            xg = x0 + random.random() * self.rad * 2
            yg = y0 + random.random() * self.rad * 2
            if math.sqrt((xg - self.xc) ** 2 + (yg - self.yc) ** 2) <= self.rad:
                return [xg, yg]

Go solution

matched/original

package main

import (
    "math"
    "math/rand"
    "time"
)

type Solution struct {
    rad, xc, yc float64
}

func Constructor(radius float64, x_center float64, y_center float64) Solution {
    rand.Seed(time.Now().UnixNano())
    return Solution{rad: radius, xc: x_center, yc: y_center}
}

func (s *Solution) RandPoint() []float64 {
    x0 := s.xc - s.rad
    y0 := s.yc - s.rad

    for {
        xg := x0 + rand.Float64()*s.rad*2
        yg := y0 + rand.Float64()*s.rad*2
        if math.Sqrt(math.Pow(xg-s.xc, 2)+math.Pow(yg-s.yc, 2)) <= s.rad {
            return []float64{xg, yg}
        }
    }
}

Explanation

Algorithm

Генерируем равномерно случайные точки в квадрате S с длиной стороны 2R.

Сохраняем все точки, которые находятся на расстоянии не более R от центра, и отклоняем все, которые дальше этого расстояния.

Повторяем процесс до получения нужного количества точек, учитывая, что примерно 78.5% от всех сгенерированных точек будут приемлемыми, и ожидаемое число попыток до получения приемлемой точки составляет примерно 1.274 раза.

😎