{"id":230,"date":"2012-05-26T11:52:37","date_gmt":"2012-05-26T03:52:37","guid":{"rendered":"http:\/\/www.shuizilong.com\/house\/?p=230"},"modified":"2012-05-26T18:30:26","modified_gmt":"2012-05-26T10:30:26","slug":"poj-3525-most-distant-point-from-the-sea","status":"publish","type":"post","link":"https:\/\/www.shuizilong.com\/house\/archives\/poj-3525-most-distant-point-from-the-sea\/","title":{"rendered":"POJ 3525. Most Distant Point from the Sea"},"content":{"rendered":"<h3>Brief description : <\/h3>\n<p>\u51f8\u591a\u8fb9\u5f62\u5185\u627e\u8ddd\u79bb\u591a\u53d8\u5f62\u8fb9\u6700\u8fdc\u7684\u4e00\u70b9\u3002\uff08\u6c42\u80fd\u653e\u5728\u51f8\u591a\u8fb9\u5f62\u91cc\u6700\u5927\u5706\u7684\u534a\u5f84\u3002\u3002\uff09<\/p>\n<p><!--more--><\/p>\n<h3>Analysis :<\/h3>\n<p>\u3002\u3002\u3002\u8c8c\u4f3c\u6b63\u89e3\u662f\u4e8c\u5206+\u534a\u5e73\u9762\u4ea4\u5224\u5b9a\uff1f\u3002\u3002\uff08<\/p>\n<p>\u8fd9\u91cc\u5148\u6d4b\u4e0b\u9000\u706b\u3002\u3002\u3002\u603b\u4e4b\u8fd9\u4e2a\u95ee\u9898\u4ea7\u751f\u504f\u79bb\u5411\u91cf\u6709\u4e24\u79cd\u65b9\u6cd5\u3002\u3002<\/p>\n<p>1. \u65e0\u5dee\u522b360\u00b0\u968f\u5373\u4ea7\u751f\u4e00\u4e2a\u3002\u3002\u3002<br \/>\n2. \u5bf9\u591a\u8fb9\u5f62\u626b\u4e00\u904d\u52a0\u6743\u4ea7\u751f\u4e00\u4e2a\u3002\u3002\u3002<\/p>\n<p>\u540e\u8005\u5b58\u5728\u4e00\u4e2a O(n) \u7684\u4ee3\u4ef7\u3002\u3002\u4f46\u662f\u8c8c\u4f3c\u53ef\u4ee5\u4e00\u5b9a\u7a0b\u5ea6\u4e0a\u4fdd\u8bc1\u5728\u591a\u8fb9\u5f62\u91cc\u9762\u3002\u3002\uff08\u8003\u8651\u90a3\u79cd\u730e\u5947\u7684\u949d\u89d2\u4e09\u89d2\u5f62\u5427\u3002\u3002\u3002<br \/>\n\u3002\u3002\u3002\u4e8e\u662f\u6211\u7684\u7b56\u7565\u662f \u4f18\u5148\u91c7\u7528 \u7b56\u7565 1. \u3002\u3002\u3002\u5f53\u5224\u5b9a\u51fa\u754c\u7684\u60c5\u51b5\u4e0b\u4e0b\u6b21\u91c7\u7528\u7b56\u7565 2.\u3002\u3002\uff09<\/p>\n<pre class=\"brush: cpp; collapse: true; first-line: 1; light: false; title: POJ 3525.cpp; toolbar: true; notranslate\" title=\"POJ 3525.cpp\">\r\nconst int N = 109, L = 200, W = 1000, _T = 3000;\r\nconst DB V = 0.8;\r\n\r\n\/\/ L: \u8fed\u4ee3\u6b21\u6570\r\n\/\/ W: \u53ef\u5206\u914d\u6743\u503c\r\n\/\/ _T: \u521d\u59cb\u6e29\u5ea6\u3002\u3002\r\n\r\n\/\/ V: \u964d\u706b\u901f\u7387\u3002\u3002\r\n\r\nstruct Polygon;\r\nDB dist_sqr(Polygon, Po);\r\n\r\nstruct Polygon{\r\n    Po P&#x5B;N]; int n;\r\n\r\n    DB dist_sqr(Po p){\r\n        return ::dist_sqr((*this), p);\r\n    }\r\n\r\n    void init(int _n){\r\n        n = _n; REP(i, n) P&#x5B;i].input(); P&#x5B;n] = P&#x5B;0];\r\n    }\r\n\r\n    bool inside(Po p){\r\n        REP(i, n) if (det(P&#x5B;i], P&#x5B;i+1], p) &lt; 0) return false;\r\n        return true;\r\n    }\r\n\r\n    void solve(){\r\n\r\n        Po res; int l = 0; REP(i, n){\r\n            int w = rand() % W + 1;\r\n            res += w * P&#x5B;i], l += w;\r\n        }\r\n\r\n        res \/= l;\r\n\r\n        DB T = _T, best = dist_sqr(res);\r\n\r\n        while (T &gt; EPS){\r\n\r\n            bool improved = false;\r\n            bool hard = false;\r\n\r\n            Po pre = res, cur; DO_C(L){\r\n                if (!hard){\r\n                    DB theta = (DB) (rand() % W) \/ W * (2*PI);\r\n                    cur = pre + Po(cos(theta), sin(theta)) * T;\r\n                }\r\n                else {\r\n\r\n                    Po dir; REP(i, n){\r\n                        int w = rand() % W + 1;\r\n                        dir += (P&#x5B;i] - pre) * w;\r\n                    }\r\n\r\n                    if (sgn(dir.length_sqr()) == 0) continue;\r\n                    if (dice()) dir = - dir;\r\n\r\n                    dir \/= dir.length(), dir *= T;\r\n                    cur = pre + dir;\r\n                }\r\n\r\n                if (inside(cur)){\r\n                    DB temp = dist_sqr(cur);\r\n                    if (temp &gt; best){\r\n                        improved = true;\r\n                        res = cur, best = temp;\r\n                    }\r\n                    hard = false;\r\n                }\r\n                else\r\n                    hard = true;\r\n            }\r\n\r\n            if (!improved) T *= V;\r\n        }\r\n\r\n        OT(sqrt(best));\r\n    }\r\n} P;\r\n\r\nDB dist_sqr(Polygon Poly, Po p){\r\n    DB res = OO; REP(i, Poly.n) res = min(res, dist_sqr(Seg(Poly.P&#x5B;i], Poly.P&#x5B;i+1]), p));\r\n    return res;\r\n}\r\n\r\nint n;\r\n\r\nint main(){\r\n\r\n#ifdef LOCAL\r\n    freopen(&quot;in.txt&quot;, &quot;r&quot;, stdin);\r\n#endif\r\n\r\n    while (true){\r\n        if (!_RD(n)) break;\r\n        P.init(n); P.solve();\r\n    }\r\n}\r\n<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>Brief description : \u51f8\u591a\u8fb9\u5f62\u5185\u627e\u8ddd\u79bb\u591a\u53d8\u5f62\u8fb9\u6700\u8fdc\u7684\u4e00\u70b9\u3002\uff08\u6c42\u80fd\u653e\u5728\u51f8\u591a\u8fb9\u5f62\u91cc\u6700\u5927\u5706\u7684\u534a\u5f84\u3002\u3002\uff09<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_publicize_message":"","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":false,"jetpack_social_options":{"image_generator_settings":{"template":"highway","enabled":false}}},"categories":[19],"tags":[72],"class_list":["post-230","post","type-post","status-publish","format-standard","hentry","category-poj","tag-72"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/p2tdP7-3I","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/230","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/comments?post=230"}],"version-history":[{"count":0,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/230\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/media?parent=230"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/categories?post=230"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/tags?post=230"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}