Problem I<\/strong><\/a><\/p>\n\n\n\n\u4ee5\u52a0\u901f\u5ea6\u4e3a\u7b2c\u4e00\u5173\u952e\u5b57\u5347\u5e8f\uff0c\u4ee5\u521d\u59cb\u4f4d\u7f6e\u4e3a\u7b2c\u4e8c\u5173\u952e\u5b57\u5347\u5e8f\u6392\u5e8f\u3002\u91cd\u590d\u5143\u7d20\u4fdd\u7559\u4e00\u4e2a\u5e76\u6253\u4e0a\u6807\u8bb0\u3002\u590d\u6742\u5ea6O(n log n)\u3002<\/p>\n\n\n\n
\u4ece\u5de6\u81f3\u53f3\u904d\u5386\u6240\u6709\u5143\u7d20\u3002\u5c06\u5f53\u524d\u5143\u7d20\u8bb0\u4e3ae\uff0c\u6808\u9876\u7684\u4e24\u4e2a\u5143\u7d20\uff08\u5982\u679c\u5b58\u5728\uff09\u5206\u522b\u8bb0\u4e3at1\u548ct2\u3002\u5982\u679ce\u7684\u521d\u59cb\u4f4d\u7f6e\u4e0d\u6bd4t1\u4f4e\uff0c\u90a3\u4e48e\u603b\u662f\u4f1a\u5728t1\u7684\u4e0a\u65b9\uff0ct1\u51fa\u6808\uff1b\u5982\u679ct1\u8ffd\u8d76t2\u6240\u9700\u7684\u65f6\u95f4\u6bd4e\u8ffd\u8d76t1\u6240\u9700\u7684\u65f6\u95f4\u8fd8\u5c11\uff0c\u90a3\u4e48t1\u4e5f\u51fa\u6808\u3002\u5bf9\u4e8e\u6bcf\u4e2a\u5143\u7d20\u603b\u662f\u8fdb\u884c\u8fd9\u6837\u7684\u68c0\u67e5\uff0c\u76f4\u5230\u4e0d\u518d\u6709\u5143\u7d20\u51fa\u6808\u4e3a\u6b62\uff0c\u590d\u6742\u5ea6O(n)\u3002<\/p>\n\n\n\n
WA\u70b9\uff1a\u672c\u5783\u573e\u65f6\u9694\u6570\u6708\u53c8\u5fd8\u8bb0long long\u4e86\u3002>=\u6f0f\u4e2a=\u4ec0\u4e48\u7684\u4e5f\u2026\u2026<\/p>\n\n\n\n
\/* HDU 2020 - Training 1\n * Problem I\n * Au: SJoshua\n *\/\n#include <bits\/stdc++.h>\n#ifndef open_dbg_func\n#define dbg(...) (__VA_ARGS__)\n#endif\n\nusing namespace std;\n\nstruct Robot {\n long long p, a;\n bool dup;\n bool operator < (const Robot &r) const {\n return a == r.a ? p < r.p : a < r.a;\n }\n bool operator == (const Robot &r) const {\n return p == r.p && a == r.a;\n }\n friend ostream& operator << (ostream &stream, const Robot &r) {\n return stream << \"(a = \" << r.a << \", p = \" << r.p << \", dup = \" << (r.dup ? \"true\" : \"false\") << \")\";\n }\n};\n\nbool judge(Robot &a, Robot &b, Robot &c) {\n return (b.p - c.p) * (b.a - a.a) - (a.p - b.p) * (c.a - b.a) <= 0;\n}\n\nint main() {\n ios::sync_with_stdio(false);\n cin.tie(nullptr);\n int T;\n cin >> T;\n while (T--) {\n int n;\n cin >> n;\n vector <Robot> robots(n);\n for (int i = 0; i < n; i++) {\n cin >> robots[i].p >> robots[i].a;\n }\n sort(robots.begin(), robots.end());\n for (int i = 1; i < n; i++) {\n if (robots[i - 1] == robots[i]) {\n robots[i - 1].dup = robots[i].dup = true;\n }\n }\n robots.resize(unique(robots.begin(), robots.end()) - robots.begin());\n vector <Robot> stack;\n for (auto e: robots) {\n while ((!stack.empty() && e.p >= stack.back().p) || (stack.size() > 1 && judge(stack[stack.size() - 2], stack[stack.size() - 1], e))) {\n stack.pop_back();\n }\n stack.push_back(e);\n }\n int ans = 0;\n for (auto e: stack) {\n ans += !e.dup;\n }\n cout << ans << endl;\n }\n return 0;\n}<\/pre>\n\n\n\n<\/p>","protected":false},"excerpt":{"rendered":"
\u6211\u4e00\u5411\u662f\u4e0d\u600e\u4e48\u5728\u8fd9\u91cc\u653eCoding\u76f8\u5173\u7684\u4e1c\u897f\u7684\uff08\u5305\u542b\u7b97\u6cd5\u7ade\u8d5b\u548c\u4fe1\u606f\u5b89\u5168\u7ade\u8d5b\uff09\u3002 \u53ef\u662f\u672c\u61d2\u866b\u6e10\u6e10\u5730\u5c31\u5931\u53bb\u4e86\u5728\u535a\u5ba2\u5199\u65e5\u5e38\u7684\u52a8\u529b\uff1b\u529f\u5229\u70b9\u8bf4\u4ee5\u540e\u627e\u5de5\u4f5c\u7684\u65f6\u5019\u653e\u4e2a\u9664\u4e86\u9ed1\u5386\u53f2\u4ec0\u4e48\u90fd\u770b\u4e0d\u5230\u7684\u535a\u5ba2\u4e5f\u4e0d\u592a\u597d\u2026\u2026 \u4ee5\u540e\u4e5f\u7a0d\u5fae\u628aOneNote … <\/p>\n
“2020\u5e74\u676d\u7535\u591a\u6821\u7b2c\u4e00\u573a” \u306e<\/span>\u7d9a\u304d\u3092\u8aad\u3080<\/a><\/p>","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[3],"tags":[186,209],"class_list":["post-2149","post","type-post","status-publish","format-standard","hentry","category-coding","tag-186","tag-209"],"_links":{"self":[{"href":"https:\/\/sforest.in\/ja\/wp-json\/wp\/v2\/posts\/2149","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/sforest.in\/ja\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/sforest.in\/ja\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/sforest.in\/ja\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/sforest.in\/ja\/wp-json\/wp\/v2\/comments?post=2149"}],"version-history":[{"count":0,"href":"https:\/\/sforest.in\/ja\/wp-json\/wp\/v2\/posts\/2149\/revisions"}],"wp:attachment":[{"href":"https:\/\/sforest.in\/ja\/wp-json\/wp\/v2\/media?parent=2149"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/sforest.in\/ja\/wp-json\/wp\/v2\/categories?post=2149"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/sforest.in\/ja\/wp-json\/wp\/v2\/tags?post=2149"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}