{"id":277,"date":"2024-03-20T17:40:54","date_gmt":"2024-03-20T09:40:54","guid":{"rendered":"https:\/\/linxce.ink\/?p=277"},"modified":"2024-03-20T17:43:11","modified_gmt":"2024-03-20T09:43:11","slug":"%e5%b9%b3%e9%9d%a2%e6%9c%80%e8%bf%91%e7%82%b9%e5%af%b9","status":"publish","type":"post","link":"https:\/\/linxce.ink\/index.php\/%e5%b9%b3%e9%9d%a2%e6%9c%80%e8%bf%91%e7%82%b9%e5%af%b9\/%e5%85%a8%e9%83%a8\/acm\/","title":{"rendered":"\u5e73\u9762\u6700\u8fd1\u70b9\u5bf9"},"content":{"rendered":"

<\/p>\n

\u5206\u6cbb\u552f\u4e00\u771f\u795e\uff0c\u62d2\u7edd\u4eba\u7c7b\u667a\u6167<\/h3>\n

\u8003\u8651\u5206\u6cbb\u65b9\u6cd5\uff1a\u4e0e\u5e38\u89c4\u7684\u5206\u6cbb\u7b97\u6cd5\u4e00\u6837\uff0c\u6211\u4eec\u5c06\u8fd9\u4e2a\u6709 <\/path><\/defs><\/use><\/g><\/svg><\/span><\/path><\/path><\/path><\/defs><\/use><\/use>\u548c<\/text><\/g><\/use><\/use><\/g><\/g><\/svg><\/span>

\u8fd9\u6837\u5206\u6210\u4e86\u4e09\u4e2a\u95ee\u9898\uff1a<\/p>\n

\n
    \n
  1. \u4e24\u4e2a\u70b9\u90fd\u5728<\/path><\/path><\/defs><\/use><\/use><\/g><\/svg><\/span>
  2. \u4e24\u4e2a\u70b9\u5206\u522b\u5728<\/path><\/path><\/path><\/defs><\/use><\/use>\u548c<\/text><\/g><\/use><\/use><\/g><\/g><\/svg><\/span>
  3. \u4e24\u4e2a\u70b9\u90fd\u5728<\/path><\/path><\/defs><\/use><\/use><\/g><\/svg><\/span>

    <\/path><\/path><\/path><\/defs><\/use><\/use><\/use><\/g><\/svg><\/span><\/path><\/defs><\/use><\/g><\/svg><\/span><\/path><\/defs><\/use><\/g><\/svg><\/span><\/path><\/path><\/path><\/defs><\/use><\/use><\/use><\/g><\/svg><\/span><\/path><\/path><\/path><\/path><\/path><\/path><\/path><\/path><\/path><\/path><\/path><\/defs><\/use><\/use><\/use><\/use><\/use><\/use><\/use><\/use><\/use><\/use><\/use><\/use><\/g><\/svg><\/span><\/path><\/defs><\/use><\/g><\/svg><\/span><\/path><\/defs><\/use><\/g><\/svg><\/span><\/path><\/path><\/path><\/path><\/path><\/path><\/path><\/path><\/defs><\/use><\/use><\/use><\/use><\/g><\/use><\/use><\/use><\/use><\/use><\/g><\/use><\/use><\/g><\/svg><\/span><\/path><\/path><\/path><\/defs><\/use><\/use><\/use><\/use><\/g><\/svg><\/span>

    \u65f6\u95f4\u590d\u6742\u5ea6 <\/path><\/path><\/path><\/path><\/path><\/path><\/path><\/defs><\/use><\/use><\/use><\/use><\/use><\/use><\/use><\/use><\/g><\/svg><\/span>
    \n\u5206\u6cbb\u65b9\u6cd5\u2160\uff1a\u6bd4\u8d77\u7b2c\u4e8c\u79cd\u8f83\u6162\u4f46\u662f\u7801\u91cf\u5c11\u4e00\u70b9<\/p>\n

    struct Point\n{\n    double x, y;\n};\ntypedef vector<Point>::iterator Iter;\nbool cmpx(const Point a, const Point b) { return a.x < b.x; }\nbool cmpy(const Point a, const Point b) { return a.y < b.y; }\ndouble dis(const Point a, const Point b)\n{\n    return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));\n}\nvoid slv(const Iter l, const Iter r, double &d)\n{\n    if (r - l <= 1) return;\n    vector<Point> Q;\n    Iter t = l + (r - l) \/ 2;\n    double w = t->x;\n    slv(l, t, d), slv(t, r, d), inplace_merge(l, t, r, cmpy);\n    for (Iter x = l; x != r; ++x) if (abs(w - x->x) <= d) Q.push_back(*x);\n    for (Iter x = Q.begin(), y = x; x != Q.end(); ++x)\n    {\n        while (y != Q.end() && y->y <= x->y + d) ++y;\n        for (Iter z = x + 1; z != y; ++z) d = min(d, dis(*x, *z));\n    }\n}\nvector<Point> Poi; int n;\ndouble preparata()\n{\n    double ans = 1e18;\n    sort(Poi.begin(),Poi.end(), cmpx);\n    slv(Poi.begin(),Poi.end(), ans);\n    return ans;\n}\n<\/code><\/pre>\n
    \u5206\u6cbb\u65b9\u6cd5\u2161\uff1a\u6bd4\u7b2c\u4e00\u79cd\u66f4\u5feb\u4f46\u662f\u7801\u91cf\u5927\u4e00\u70b9<\/p>\n
    struct pt\n{\n    double x, y;\n    int id;\n};\nbool cmpx(const pt a, const pt b) { return a.x < b.x; }\nbool cmpy(const pt a, const pt b) { return a.y < b.y; }\nint n, ansa, ansb; \/\/ \u7b54\u6848\u5728\u8fd9\nvector<pt> a;     \/\/ \u4e0b\u68070\u5f00\u59cb\ndouble mindist;\nvoid upd_ans(const pt &a, const pt &b)\n{\n    double dist = sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));\n    if (dist < mindist)\n        mindist = dist, ansa = a.id, ansb = b.id;\n}\nvoid rec(int l, int r)\n{\n    if (r - l <= 3) \/\/\u70b9\u6570\u5c0f\u4e8e3\u76f4\u63a5\u66b4\u529b\u627e\n    {\n        for (int i = l; i <= r; ++i)\n            for (int j = i + 1; j <= r; ++j)\n                upd_ans(a[i], a[j]);\n        sort(a.begin() + l, a.begin() + r + 1, cmpy);\n        return;\n    }\n    int m = (l + r) >> 1;\n    double midx = a[m].x;\n    rec(l, m), rec(m + 1, r);\n    \/\/\u5f52\u5e76\u6392\u5e8f\n    inplace_merge(a.begin() + l, a.begin() + m + 1, a.begin() + r + 1, cmpy);\n    static pt t[N]; \/\/ \u7f13\u5b58\u6570\u7ec4\n    int tsz = 0;\n    for (int i = l; i <= r; ++i)\n        if (abs(a[i].x - midx) < mindist) \/\/\u53ef\u80fd\u662f\u6700\u8fd1\u70b9\u5bf9\n        {\n            for (int j = tsz - 1; j >= 0 && a[i].y - t[j].y < mindist; --j) upd_ans(a[i], t[j]);\n            t[tsz++] = a[i];\n        }\n}\nvoid preparata()\n{\n    sort(a.begin(), a.end(), cmpx);\n    mindist = (ll)1e18;\n    rec(0, n - 1);\n}\n<\/code><\/pre>\n
    \u975e\u5206\u6cbb\uff1a\u66f4\u5feb\uff08\u5e38\u6570\u5c0f\uff09<\/p>\n
    <\/p>\n
    int n;\ndouble ans = 1e20;\nstruct Point\n{\n    double x, y;\n    Point(double x = 0, double y = 0) : x(x), y(y) {}\n};\nstruct cmp_y { bool operator()(const Point &a, const Point &b) const { return a.y < b.y; } };\nvoid upd_ans(const Point &a, const Point &b)\n{\n    double dist = sqrt(pow((a.x - b.x), 2) + pow((a.y - b.y), 2));\n    if (ans > dist) ans = dist;\n}\nPoint a[N];\/\/\u4e0b\u68070\u5f00\u59cb\nmultiset<Point, cmp_y> s;\nvoid preparata()\n{\n    sort(a, a + n, [&](Point a, Point b) -> bool { return a.x < b.x || (a.x == b.x && a.y < b.y); });\n    for (int i = 0, l = 0; i < n; i++)\n    {\n        while (l < i && a[i].x - a[l].x >= ans) s.erase(s.find(a[l++]));\n        for (auto it=s.lower_bound({a[i].x, a[i].y - ans}); it != s.end() && it->y - a[i].y < ans; it++)\n            upd_ans(*it, a[i]);\n        s.insert(a[i]);\n    }\n}\n<\/code><\/pre>\n
    <\/html><\/p>\n","protected":false},"excerpt":{"rendered":"
    \u5206\u6cbb\u552f\u4e00\u771f\u795e\uff0c\u62d2\u7edd\u4eba\u7c7b\u667a\u6167 \u8003\u8651...<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[5,25,26],"tags":[21,7,27],"class_list":["post-277","post","type-post","status-publish","format-standard","hentry","category-acm","category-25","category-26","tag-acm","tag-cpp","tag-27"],"_links":{"self":[{"href":"https:\/\/linxce.ink\/index.php\/wp-json\/wp\/v2\/posts\/277","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/linxce.ink\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/linxce.ink\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/linxce.ink\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/linxce.ink\/index.php\/wp-json\/wp\/v2\/comments?post=277"}],"version-history":[{"count":6,"href":"https:\/\/linxce.ink\/index.php\/wp-json\/wp\/v2\/posts\/277\/revisions"}],"predecessor-version":[{"id":284,"href":"https:\/\/linxce.ink\/index.php\/wp-json\/wp\/v2\/posts\/277\/revisions\/284"}],"wp:attachment":[{"href":"https:\/\/linxce.ink\/index.php\/wp-json\/wp\/v2\/media?parent=277"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/linxce.ink\/index.php\/wp-json\/wp\/v2\/categories?post=277"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/linxce.ink\/index.php\/wp-json\/wp\/v2\/tags?post=277"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}