{"id":1244,"date":"2020-05-17T12:48:24","date_gmt":"2020-05-17T19:48:24","guid":{"rendered":"http:\/\/209.126.2.187\/?p=1244"},"modified":"2020-05-17T12:49:27","modified_gmt":"2020-05-17T19:49:27","slug":"pure-geometry","status":"publish","type":"post","link":"https:\/\/nanzhou.cc\/index.php\/2020\/05\/17\/pure-geometry\/","title":{"rendered":"Pure Geometry"},"content":{"rendered":"\n<h4 class=\"wp-block-heading\"><a rel=\"noreferrer noopener\" href=\"https:\/\/leetcode.com\/problems\/maximum-number-of-darts-inside-of-a-circular-dartboard\/\" target=\"_blank\">LC 1453. Maximum Number of Darts Inside of a Circular Dartboard<\/a><\/h4>\n\n\n\n<p>Given 2 points and 1 radius, there will be 2 or 1 or 0 circles where the 2 points are at the boundary.  When <code>dist(p0, p1)&gt;2r<\/code>, there will be 0 circles.  <\/p>\n\n\n\n<p>The difficulty is how to get the center of the circle in clean C++ codes. A good class we could use is <code>std::complex&lt;T&gt;<\/code>.  Each point is a vector in the 2d grid. <\/p>\n\n\n\n<figure class=\"wp-block-image size-large\"><img loading=\"lazy\" decoding=\"async\" width=\"621\" height=\"447\" src=\"http:\/\/161.97.122.139\/wp-content\/uploads\/2020\/05\/image.png\" alt=\"\" class=\"wp-image-1248\" srcset=\"https:\/\/nanzhou.cc\/wp-content\/uploads\/2020\/05\/image.png 621w, https:\/\/nanzhou.cc\/wp-content\/uploads\/2020\/05\/image-300x216.png 300w\" sizes=\"auto, (max-width: 621px) 100vw, 621px\" \/><\/figure>\n\n\n\n<pre class=\"wp-block-code\"><code class=\"\">\/\/ d = |p0_p1|\n\/\/ h = sqrt(r^2 - d^2\/4)\n\/\/ p3_ = (p1_ + p0) \/ 2.0\n\/\/ p3_c = p0_p1 * (0, j) * h\/d\n\/\/ c = p3_ + p3_c\nusing P = complex&lt;double>;\nP get_center0(P const &amp;p0, P const &amp;p1, int r) {\n    auto d = abs(p0 - p1);\n    auto p3 = (p1 + p0) \/ 2.0;\n    auto c = p3 + (p0 - p1) * P(0, 1) * sqrt(r * r - d * d \/ 4) \/ d;\n    return c;\n}<\/code><\/pre>\n\n\n\n<p> Some techniques we will use. <\/p>\n\n\n\n<pre class=\"wp-block-code\"><code class=\"\">\/\/ equal is meaningless in double, we use \"&lt; epsilon\" instead of \"&lt;=\"\ndist(p3, c) &lt; r + EPS\n\/\/ there will be two centers: p3_c = p0_p1 * (0, -j) * h\/d\n\/\/ but it will be covered when we enumerate (j, i)<\/code><\/pre>\n\n\n\n<p><\/p>\n","protected":false},"excerpt":{"rendered":"<p>LC 1453. Maximum Number of Darts Inside of a Circular Dartboard Given 2 points and 1 radius, there will be 2 or 1 or 0 circles where the 2 points are at the boundary. When dist(p0, p1)&gt;2r, there will be 0 circles. The difficulty is how to get the center of the circle in clean&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[48,63],"tags":[],"class_list":["post-1244","post","type-post","status-publish","format-standard","hentry","category-alg","category-computational-geometry"],"_links":{"self":[{"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/posts\/1244","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/comments?post=1244"}],"version-history":[{"count":3,"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/posts\/1244\/revisions"}],"predecessor-version":[{"id":1251,"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/posts\/1244\/revisions\/1251"}],"wp:attachment":[{"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/media?parent=1244"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/categories?post=1244"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/tags?post=1244"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}