{"id":3014,"date":"2023-06-09T18:41:13","date_gmt":"2023-06-09T10:41:13","guid":{"rendered":"https:\/\/www.shuizilong.com\/house\/?p=3014"},"modified":"2023-06-10T09:54:50","modified_gmt":"2023-06-10T01:54:50","slug":"luogu-p1995-noi2011-%e6%99%ba%e8%83%bd%e8%bd%a6%e6%af%94%e8%b5%9b","status":"publish","type":"post","link":"https:\/\/www.shuizilong.com\/house\/archives\/luogu-p1995-noi2011-%e6%99%ba%e8%83%bd%e8%bd%a6%e6%af%94%e8%b5%9b\/","title":{"rendered":"Luogu P1995. [NOI2011] \u667a\u80fd\u8f66\u6bd4\u8d5b"},"content":{"rendered":"<ul>\n<li><a href=\"https:\/\/www.luogu.com.cn\/problem\/P1995\">https:\/\/www.luogu.com.cn\/problem\/P1995<\/a><\/li>\n<\/ul>\n<p>\u5148\u590d\u4e60\u4e00\u4e0b <a href=\"https:\/\/vijos.org\/p\/1013\">\u8fd9\u4e2a\u9898<\/a>\u3002\u3002\u3002<\/p>\n<pre class=\"brush: cpp; light: false; title: ; toolbar: true; notranslate\" title=\"\">\r\n#include &lt;lastweapon\/geometry&gt;\r\nusing namespace lastweapon;\r\nusing namespace CG;\r\n\r\nconst int N = 21;\r\n\r\nDB dp&#x5B;N]&#x5B;4], x&#x5B;N], y&#x5B;N]&#x5B;4];\r\nint n;\r\n\r\nbool ok(int i0, int j0, int i1, int j1) {\r\n    Line s(Po(x&#x5B;i0], y&#x5B;i0]&#x5B;j0]), Po(x&#x5B;i1], y&#x5B;i1]&#x5B;j1]));\r\n    FOR(i, i0+1, i1) {\r\n        if(Seg(Po(x&#x5B;i], y&#x5B;i]&#x5B;0]), Po(x&#x5B;i], y&#x5B;i]&#x5B;1])).sgn(s) &lt; 0 &amp;&amp;\r\n           Seg(Po(x&#x5B;i], y&#x5B;i]&#x5B;2]), Po(x&#x5B;i], y&#x5B;i]&#x5B;3])).sgn(s) &lt; 0) return 0;\r\n    }\r\n    return 1;\r\n}\r\n\r\nint main() {\r\n\r\n#ifndef ONLINE_JUDGE\r\n    \/\/freopen(&quot;in.txt&quot;, &quot;r&quot;, stdin);\r\n    \/\/freopen(&quot;out.txt&quot;, &quot;w&quot;, stdout);\r\n#endif\r\n\r\n    RD(n); REP(j, 4) y&#x5B;0]&#x5B;j] = 5;\r\n    REP_1(i, n) {\r\n        RF(x&#x5B;i]); REP(j, 4) RF(y&#x5B;i]&#x5B;j]);\r\n    }\r\n    x&#x5B;++n] = 10; REP(j, 4) y&#x5B;n]&#x5B;j] = 5;\r\n    REP_1(i, n) REP(j, 4) dp&#x5B;i]&#x5B;j] = OO;\r\n\r\n    FOR(i, 0, n) REP(j, 4) FOR_1(ii, i+1, n) REP(jj, 4) {\r\n        if (ok(i, j, ii, jj)) checkMin(dp&#x5B;ii]&#x5B;jj], dp&#x5B;i]&#x5B;j] + dist(Po(x&#x5B;i], y&#x5B;i]&#x5B;j]), Po(x&#x5B;ii], y&#x5B;ii]&#x5B;jj])));\r\n    }\r\n\r\n    printf(&quot;%.2f\\n&quot;, dp&#x5B;n]&#x5B;0]);\r\n}\r\n\r\n<\/pre>\n<p>\u7136\u540e\u53ef\u4ee5\u5148\u76f4\u63a5\u8f93\u51fa dist(s, t) \u6012\u9a97 20 \u5206\u3002\u3002\u3002\uff08\u56e0\u4e3a\u4f60\u6570\u636e\u91cc\u80af\u5b9a\u4e5f\u5fc5\u987b\u6709\u8fd9\u79cd\u7c7b\u578b\u7684\u6570\u636e\u5427\u3002\u3002\u3002\uff09<\/p>\n<pre class=\"brush: cpp; light: false; title: ; toolbar: true; notranslate\" title=\"\">\r\n#include &lt;lastweapon\/geometry&gt;\r\nusing namespace lastweapon;\r\nusing namespace CG;\r\n\r\nconst int N = int(2e3) + 9;\r\n\r\nstruct Rect {\r\n    int x0, y0, x1, y1;\r\n    void in() {\r\n        RD(x0, y0, x1, y1);\r\n    }\r\n} R&#x5B;N];\r\nDB f&#x5B;N]&#x5B;2]; Po s, t;\r\nint n;\r\n\r\nDB gao() {\r\n    return dist(s, t);\r\n}\r\n\r\nint main() {\r\n\r\n#ifndef ONLINE_JUDGE\r\n    \/\/freopen(&quot;in.txt&quot;, &quot;r&quot;, stdin);\r\n    \/\/freopen(&quot;out.txt&quot;, &quot;w&quot;, stdout);\r\n#endif\r\n\r\n    RD(n); REP(i, n) R&#x5B;i].in(); s.in(); t.in();\r\n    printf(&quot;%9f\\n&quot;, gao() \/ RF());\r\n}\r\n<\/pre>\n<p>\u6838\u5fc3\u7684\u533a\u522b\u5c31\u662f vijos \u90a3\u4e2a\u9898\uff0c\u6211\u53ef\u4ee5 O(n3) dp\uff0c\u66b4\u529b check \u4e24\u70b9\u4e4b\u95f4\u7684\u53ef\u8fbe\u6027\u3002.\u800c NOI \u8fd9\u4e2a\u9898\uff0c\u6bcf\u6b21\u53ea\u6709\u4e00\u6bb5\u7a7a\u9699\uff0c\u6240\u4ee5\u53ef\u901a\u8fc7\u533a\u57df\u662f\u4e00\u4e2a\u4e0d\u65ad\u7f29\u5c0f\u7684\u6247\u5f62\u3002\u3002\u4e8e\u662f\u590d\u6742\u5ea6\u5c31 O(n2) \u4e86\u3002<\/p>\n<p>\u987a\u4fbf\u539f\u7248 vijos \u7684\u90a3\u4e2a\u7248\u672c\uff0c\u5176\u5b9e\u6211\u4eec\u4e5f\u53ef\u4ee5\u7528\u5e73\u8861\u6728\u6765\u7ef4\u62a4\u53ef\u901a\u8fc7\u7684\u533a\u57df\u3002\u3002\u3002<br \/>\n\u56de\u5230\u5b9e\u73b0\u3002\u3002\u5b64\u7acb\u7684 s \u70b9\u548c t \u70b9\u5f88\u70e6\u3002\u3002\u800c\u4e14\u6709\u5f88\u591a corner case\u3002\u3002<\/p>\n<p>\u6211\u4eec\u60f3\u529e\u6cd5\u628a s \u548c t \u90fd\u89c6\u4e3a\u4e00\u4e2a\u9000\u5316\u7684\u77e9\u5f62\u3002\u3002\u3002\u3002\u8fd9\u6837\u6211\u5c31\u4e0d\u7528\u5199\u989d\u5916\u7684\u4ee3\u7801\u4e86\u3002<\/p>\n<pre class=\"brush: cpp; light: false; title: ; toolbar: true; notranslate\" title=\"\">\r\n#include &lt;lastweapon\/geometry&gt;\r\nusing namespace lastweapon;\r\nusing namespace CG;\r\n\r\nconst int N = int(2e3) + 9;\r\n\r\nstruct Rect {\r\n    int x0, y0, x1, y1;\r\n    void in() {\r\n        RD(x0, y0, x1, y1);\r\n    }\r\n} R&#x5B;N];\r\nDB f&#x5B;N]&#x5B;2]; int l&#x5B;N], r&#x5B;N]; Po s, t;\r\n\r\nint n;\r\n\r\nbool cmp(const Rect R, int x) {\r\n    return R.x1 &lt; x;\r\n}\r\n\r\nDB gao() {\r\n\r\n    int si = lower_bound(R+1, R+n+1, s.x, cmp) - R;\r\n    int ti = lower_bound(R+1, R+n+1, t.x, cmp) - R;\r\n    if (si &gt; ti) swap(si, ti), swap(s, t);\r\n\r\n    if (R&#x5B;si].x1 != s.x) --si;\r\n    ++ti; if (R&#x5B;ti].x0 == t.x) ++ti;\r\n\r\n    R&#x5B;si].x1 = s.x; R&#x5B;si].y0 = R&#x5B;si].y1 = s.y;\r\n    R&#x5B;ti-1].x1 = t.x; R&#x5B;ti].x0 = t.x; R&#x5B;ti].y0 = R&#x5B;ti].y1 = t.y;\r\n    FOR(i, si+1, ti) f&#x5B;i]&#x5B;0] = f&#x5B;i]&#x5B;1] = OO; f&#x5B;si]&#x5B;0] = f&#x5B;si]&#x5B;1] = 0;\r\n    FOR(i, si, ti) l&#x5B;i] = max(R&#x5B;i].y0, R&#x5B;i+1].y0), r&#x5B;i] = min(R&#x5B;i].y1, R&#x5B;i+1].y1);\r\n    --ti;\r\n\r\n#define u f&#x5B;i]&#x5B;j]\r\n#define v f&#x5B;ii]&#x5B;jj]\r\n#define w dist(pu, pv)\r\n\r\n    FOR(i, si, ti) REP(j, 2) {\r\n        Po pu(R&#x5B;i].x1, j ? r&#x5B;i] : l&#x5B;i]);\r\n        DB ar = PI\/2, al = -ar;\r\n\r\n        \/\/cout &lt;&lt; pu &lt;&lt; &quot;: &quot; &lt;&lt; u &lt;&lt; endl;\r\n\r\n        FOR_1(ii, i+1, ti) REP(jj, 2) {\r\n            Po pv(R&#x5B;ii].x1, jj ? r&#x5B;ii] : l&#x5B;ii]);\r\n            DB t = atan2(pv.y-pu.y, pv.x-pu.x); if (t &gt; PI) t -= 2*PI;\r\n            if (al &lt;= t &amp;&amp; t &lt;= ar) checkMin(v, u + w);\r\n            if (jj) checkMin(ar, t); else checkMax(al, t);\r\n        }\r\n    }\r\n    return f&#x5B;ti]&#x5B;0];\r\n}\r\n\r\nint main() {\r\n\r\n#ifndef ONLINE_JUDGE\r\n    freopen(&quot;in.txt&quot;, &quot;r&quot;, stdin);\r\n    \/\/freopen(&quot;out.txt&quot;, &quot;w&quot;, stdout);\r\n#endif\r\n\r\n    RD(n); REP_1(i, n) R&#x5B;i].in(); s.in(); t.in();\r\n    printf(&quot;%9f\\n&quot;, gao() \/ RF());\r\n}\r\n\r\n\r\n<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>https:\/\/www.luogu.com.cn\/problem\/P1995 \u5148\u590d\u4e60\u4e00\u4e0b \u8fd9\u4e2a\u9898\u3002\u3002\u3002 #include &lt;lastweapon\/geometry&gt; using namespace lastweapon; using namespace CG; const int N = 21; DB dp&#x5B;N]&#x5B;4], x&#x5B;N], y&#x5B;N]&#x5B;4]; int n; bool ok(int i0, int j0, int i1, int j1) { Line s(Po(x&#x5B;i0], y&#x5B;i0]&#x5B;j0]), Po(x&#x5B;i1], y&#x5B;i1]&#x5B;j1])); FOR(i, i0+1, i1) { if(Seg(Po(x&#x5B;i], y&#x5B;i]&#x5B;0]), Po(x&#x5B;i], y&#x5B;i]&#x5B;1])).sgn(s) &lt; 0 &amp;&amp; Seg(Po(x&#x5B;i], y&#x5B;i]&#x5B;2]), Po(x&#x5B;i], y&#x5B;i]&#x5B;3])).sgn(s) &lt; 0) return [&hellip;]<\/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":true,"jetpack_social_options":{"image_generator_settings":{"template":"highway","enabled":false}}},"categories":[1],"tags":[],"class_list":["post-3014","post","type-post","status-publish","format-standard","hentry","category-uncategorized"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/p2tdP7-MC","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/3014","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=3014"}],"version-history":[{"count":6,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/3014\/revisions"}],"predecessor-version":[{"id":3020,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/3014\/revisions\/3020"}],"wp:attachment":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/media?parent=3014"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/categories?post=3014"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/tags?post=3014"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}