{"id":3336,"date":"2018-07-28T16:50:28","date_gmt":"2018-07-28T23:50:28","guid":{"rendered":"http:\/\/zxi.mytechroad.com\/blog\/?p=3336"},"modified":"2018-09-04T08:14:42","modified_gmt":"2018-09-04T15:14:42","slug":"leetcode-883-generate-random-point-in-a-circle","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/geometry\/leetcode-883-generate-random-point-in-a-circle\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 883. Generate Random Point in a Circle"},"content":{"rendered":"

Problem<\/strong><\/h1>\n

Given the radius and x-y positions of the center of a circle, write a function\u00a0randPoint<\/code>\u00a0which\u00a0generates a uniform random\u00a0point in the circle.<\/p>\n

Note:<\/p>\n

    \n
  1. input and output values are\u00a0in\u00a0floating-point<\/a>.<\/li>\n
  2. radius and x-y position of the center of the circle is passed into the class constructor.<\/li>\n
  3. a point on the circumference of the circle is considered to be\u00a0in the circle.<\/li>\n
  4. randPoint<\/code>\u00a0returns\u00a0a size 2 array containing x-position and y-position of the random point, in that order.<\/li>\n<\/ol>\n

    Example 1:<\/strong><\/p>\n

    Input: \r\n<\/strong>[\"Solution\",\"randPoint\",\"randPoint\",\"randPoint\"]\r\n<\/span>[[1,0,0],[],[],[]]<\/span>\r\nOutput: <\/strong>[null,[-0.72939,-0.65505],[-0.78502,-0.28626],[-0.83119,-0.19803]]<\/span>\r\n<\/pre>\n
    Example 2:<\/strong><\/p>\n
    Input: \r\n<\/strong>[\"Solution\",\"randPoint\",\"randPoint\",\"randPoint\"]\r\n<\/span>[[10,5,-7.5],[],[],[]]<\/span>\r\nOutput: <\/strong>[null,[11.52438,-8.33273],[2.46992,-16.21705],[11.13430,-12.42337]]<\/span><\/pre>\n
    Explanation of Input Syntax:<\/strong><\/p>\n
    The input is two lists:\u00a0the subroutines called\u00a0and their\u00a0arguments.\u00a0Solution<\/code>‘s\u00a0constructor has three arguments, the radius, x-position of the center, and y-position of the center of the circle.\u00a0randPoint<\/code>\u00a0has no arguments.\u00a0Arguments\u00a0are\u00a0always wrapped with a list, even if there aren’t any.<\/p>\n
    \u00a0<\/ins><\/p>\n
    Solution: Polar Coordinate<\/h1>\n
    uniform sample an angle a: [0, 2*Pi)<\/p>\n
    uniform sample a radius r: [0, 1)<\/p>\n
    Number of random points in a cycle should be proportional to the square of distance to the center.<\/p>\n
    e.g. there are 4 times of points with distance d than points with distance d\/2.<\/p>\n
    Thus sqrt(r) is uniformly distributed.<\/p>\n
    r’ = sqrt(r),<\/p>\n
    \n
    C++<\/h2>\n
    \n\n
    \/\/ Author: Huahua\r\n\/\/ Running time: 116 ms\r\nclass Solution {\r\npublic:\r\n  Solution(double radius, double x_center, double y_center)\r\n    :r_(radius), x_(x_center), y_(y_center) {}\r\n\r\n  vector<double> randPoint() {\r\n    double a = rand() \/ static_cast<double>(RAND_MAX) * 2 * M_PI;\r\n    double r = sqrt(rand() \/ static_cast<double>(RAND_MAX)) * r_;\r\n    return {x_ + r * cos(a), y_ + r * sin(a)};\r\n  }\r\nprivate:\r\n  double r_;\r\n  double x_;\r\n  double y_;\r\n};<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"
    Problem Given the radius and x-y positions of the center of a circle, write a function\u00a0randPoint\u00a0which\u00a0generates a uniform random\u00a0point in the circle. Note: input and…<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[127],"tags":[284,31,177,354,91],"class_list":["post-3336","post","type-post","status-publish","format-standard","hentry","category-geometry","tag-geometry","tag-math","tag-medium","tag-polar","tag-random","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/3336","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/comments?post=3336"}],"version-history":[{"count":4,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/3336\/revisions"}],"predecessor-version":[{"id":3859,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/3336\/revisions\/3859"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=3336"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=3336"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=3336"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}