\u4eca\u5929\u65b0\u63a5\u89e6\u7684\u4e00\u4e2a\u7b97\u6cd5\uff0c\u975e\u5e38\u597d\u7406\u89e3\u54c8\u54c8\uff0c\u5b9e\u73b0\u8d77\u6765\u4e5f\u633a\u65b9\u4fbf\u7684<\/p>\n\n\n\n
\u6211\u662f\u770bhttps:\/\/www.pianshen.com\/article\/763090525\/\u8fd9\u4e2a\u535a\u5ba2\u5b66\u7684\uff0c\u611f\u8c22\u8fd9\u4f4d\u5144\u5f1f\u7684\u5206\u4eab<\/p>\n\n\n\n
\u6211\u7684\u4ee3\u7801\u5982\u4e0b\uff1a<\/p>\n\n\n\n
def convexhull(points:List[Tuple[int,int]])->List[Tuple[int,int]]:\n def left_or_right(x1,y1,x2,y2,x,y):\n tmp = (y1-y2) * x + (x2-x1) * y + x1 * y2 - x2 * y1\n return tmp\n if len(points)<=3:\n return points.copy()\n points = sorted(points,key=lambda point:point[1])\n tx,ty = points[0]\n def cmp_points_atan2(point1,point2):\n a = math.atan2(point1[1]-ty,point1[0]-tx)\n b = math.atan2(point2[1]-ty,point2[0]-tx)\n if a!=b:\n return a-b\n da = (point1[1]-ty)**2+(point1[0]-tx)**2\n db = (point2[1]-ty)**2+(point2[0]-tx)**2\n return da-db\n points.sort(key=cmp_to_key(cmp_points_atan2))\n stack = deque()\n stack.append(points[0])\n stack.append(points[1])\n stack.append(points[2])\n for i in range(3,len(points)):\n pc = points[i]\n while len(stack)>=2:\n pa = stack[-2]\n pb = stack[-1]\n if left_or_right(pa[0],pa[1],pc[0],pc[1],pb[0],pb[1])<=0:\n break\n else:\n stack.pop()\n stack.append(pc)\n ret = list(stack)\n return ret<\/code><\/pre>\n\n\n\n\u4ee3\u7801\u4e34\u65f6\u4e71\u5199\u7684\uff0c\u6ca1\u4ec0\u4e48\u610f\u4e49\u3002\u4e3b\u8981\u662f\u7b97\u6cd5\u7684\u601d\u60f3\u7406\u89e3\u4e86\u5c31\u597d\u3002log(n)*n\u7684\u65f6\u95f4\u590d\u6742\u5ea6\u8fd8\u662f\u633a\u7ed9\u529b\u7684<\/p>\n","protected":false},"excerpt":{"rendered":"
\u4eca\u5929\u65b0\u63a5\u89e6\u7684\u4e00\u4e2a\u7b97\u6cd5\uff0c\u975e\u5e38\u597d\u7406\u89e3\u54c8\u54c8\uff0c\u5b9e\u73b0\u8d77\u6765\u4e5f\u633a\u65b9\u4fbf\u7684 \u6211\u662f\u770bhttps:\/\/www.piansh… \u7ee7\u7eed\u9605\u8bfb \u51f8\u5305\u7b97\u6cd5\u4e4bGraham\u626b\u63cf\u6cd5<\/span><\/i><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1],"tags":[],"class_list":{"0":"post-165","1":"post","2":"type-post","3":"status-publish","4":"format-standard","5":"hentry","6":"category-uncategorized","7":"h-entry","9":"h-as-article"},"_links":{"self":[{"href":"http:\/\/iamnear.top\/index.php?rest_route=\/wp\/v2\/posts\/165","targetHints":{"allow":["GET"]}}],"collection":[{"href":"http:\/\/iamnear.top\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/iamnear.top\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/iamnear.top\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/iamnear.top\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=165"}],"version-history":[{"count":1,"href":"http:\/\/iamnear.top\/index.php?rest_route=\/wp\/v2\/posts\/165\/revisions"}],"predecessor-version":[{"id":166,"href":"http:\/\/iamnear.top\/index.php?rest_route=\/wp\/v2\/posts\/165\/revisions\/166"}],"wp:attachment":[{"href":"http:\/\/iamnear.top\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=165"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/iamnear.top\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=165"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/iamnear.top\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=165"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}