{"id":13,"date":"2012-02-28T16:03:15","date_gmt":"2012-02-28T08:03:15","guid":{"rendered":"http:\/\/www.shuizilong.com\/house\/?p=13"},"modified":"2012-03-03T01:17:50","modified_gmt":"2012-03-02T17:17:50","slug":"ural-1369-cockroach-race","status":"publish","type":"post","link":"https:\/\/www.shuizilong.com\/house\/archives\/ural-1369-cockroach-race\/","title":{"rendered":"URAL 1369. Cockroach Race"},"content":{"rendered":"

Brief description: <\/h3>\n

\u7ed9\u5b9a\u5e73\u9762\u4e0a\u7684\u4e00\u7ec4\u70b9\u96c6 \uff0c\u5bf9\u4e8e\u6bcf\u4e2a\u8be2\u95ee\uff0c\u8f93\u51fa\u4e00\u4e2a\u65b0\u7684\u70b9\uff0c\u67e5\u8be2\u6240\u6709\u8ddd\u79bb\u5979\u6700\u8fd1\u7684\u70b9\u7684\u7f16\u53f7\u3002
\n\uff08\u70b9\u96c6\u89c4\u6a21 N <= 100000, \u8be2\u95ee\u6b21\u6570 M <= 10000)\n\n<\/p>\n

Analysis: <\/h3>\n

.. .<\/p>\n

Naive: <\/h4>\n
\r\nconst int N = 100009;\r\n\r\nPo P[N], cur;\r\nint n, m;\r\n\r\nint main() {\r\n\r\n    \/\/freopen("in.txt", "r", stdin);\r\n\r\n    REP_C(i, _RD(n)){\r\n        scanf("%lf %lf", &P[i].x, &P[i].y);\r\n    }\r\n\r\n    DO_C(RD()){\r\n        scanf("%lf %lf", &cur.x, &cur.y);\r\n        DB d = INF; REP(i, n) checkMin(d, dist_sqr(cur, P[i]));\r\n        REP(i, n) if (d == dist_sqr(cur, P[i]))\r\n            printf("%d ", i + 1);\r\n        puts("");\r\n    }\r\n}\r\n<\/pre>\n
….<\/p>\n
\r\n\r\n<\/pre>\n
Hash: <\/h4>\n
Data Structure:<\/h4>\n
\"\"<\/a><\/p>\n
\r\n...\r\nint random(int l, int r){\r\n    return rand() % (r - l + 1) + l;\r\n}\r\n\r\nstruct Rec: Po{\r\n    int id;\r\n};\r\n\r\nconst int N = 100009;\r\nconst int NN = N;\r\n\r\n\/*\r\n  |\r\n 1|0\r\n-----\r\n 3|2\r\n  |\r\n*\/\r\n\r\nRec node[NN]; DB xl[NN], xr[NN], yl[NN], yr[NN]; int c[NN][4], root, total;\r\n\/\/ Point Quadtree .. .\r\n\r\nRec P[N], temp; Po cur; DB d; VI L;\r\nint n, m;\r\n\r\ninline int Dir(Po a, Po b){\r\n    return a.x < b.x ? (a.y < b.y ? 3 : 1) : (a.y < b.y ? 2 : 0);\r\n}\r\n\r\ninline int Rev(int dir){\r\n    return dir ^ 3;\r\n}\r\n\r\nvoid Insert(int &now = root){\r\n    if (!now) now = ++total, node[now] = temp;\r\n    else Insert(c[now][Dir(temp, node[now])]);\r\n}\r\n\r\nvoid Cut(int now, int parent){\r\n    if (!now) return;\r\n\r\n    if (node[now].x < node[parent].x) xl[now] = xl[parent], xr[now] = node[parent].x; else xl[now] = node[parent].x, xr[now] = xr[parent];\r\n    if (node[now].y < node[parent].y) yl[now] = yl[parent], yr[now] = node[parent].y; else yl[now] = node[parent].y, yr[now] = yr[parent];\r\n    REP(i, 4) Cut(c[now][i], now);\r\n}\r\n\r\nvoid Update(Rec item){\r\n\r\n    DB dd = dist_sqr(cur, item);\r\n\r\n    if (sgn(dd, d) <= 0){\r\n        if (sgn(dd, d) == -1) d = dd, CLR(L);\r\n        L.PB(item.id);\r\n    }\r\n}\r\n\r\nvoid Find(int now = root){\r\n\r\n    if (!now) return;\r\n\r\n    if (xl[now] <= cur.x && cur.x <= xr[now]){\r\n        if (cur.y <= yl[now]) if (sgn(d, sqr(yl[now] - cur.y)) < 0) return;\r\n        if (yr[now] <= cur.y) if (sgn(d, sqr(cur.y - yr[now])) < 0) return;\r\n    }\r\n    else if (yl[now] <= cur.y && cur.y <= yr[now]){\r\n        if (cur.x <= xl[now]) if (sgn(d, sqr(xl[now] - cur.x)) < 0) return;\r\n        if (xr[now] <= cur.x) if (sgn(d, sqr(cur.x - xr[now])) < 0) return;\r\n    }\r\n    else if (sgn(d, min(sqr(xl[now] - cur.x), sqr(xr[now] - cur.x)) + min(sqr(yl[now] - cur.y), sqr(yr[now] - cur.y))) < 0) return;\r\n\r\n    int dir = Dir(cur, node[now]);\r\n    Find(c[now][dir]), Update(node[now]);\r\n    if (dir == 0 || dir == 3) Find(c[now][1]), Find(c[now][2]);\r\n    else if (dir == 1 || dir == 2) Find(c[now][0]), Find(c[now][3]);\r\n}\r\n\r\nint main() {\r\n\r\n    \/\/freopen("in.txt", "r", stdin);\r\n\r\n    REP_C(i, _RD(n)){\r\n        scanf("%lf %lf", &P[i].x, &P[i].y);\r\n        P[i].id = i + 1;\r\n    }\r\n\r\n    srand((unsigned)time(NULL)); REP(i, n) swap(P[i], P[random(i, n - 1)]);\r\n    REP(i, n) temp = P[i], Insert();\r\n\r\n\r\n    xl[root] = yl[root] = -10000, xr[root] = yr[root] = 10000;\r\n    REP(i, 4) Cut(c[root][i], root);\r\n\r\n    DO_C(RD()){\r\n        scanf("%lf %lf", &cur.x, &cur.y), CLR(L), d = INF; Find();\r\n        SRT(L); REP(i, SZ(L) - 1) printf("%d ", L[i]);\r\n        printf("%d\\n", L[SZ(L)-1]);\r\n    }\r\n}\r\n<\/pre>\n
\"\"<\/a><\/p>\n
\r\n...\r\nint random(int l, int r){\r\n    return rand() % (r - l + 1) + l;\r\n}\r\n\r\nstruct Rec: Po{\r\n    int id;\r\n};\r\n\r\nconst int N = 100009;\r\nconst int NN = N;\r\n\r\nRec node[NN]; DB xl[NN], xr[NN], yl[NN], yr[NN];\r\nint c[NN][2], root, total;\r\n\/\/ 2-d tree .. .\r\n\r\nRec P[N], temp; Po cur; DB d; VI L;\r\nint n, m;\r\n\r\ninline int Dir(int level, Po a, Po b){\r\n    if (level&1) return a.x < b.x ? 0 : 1;\r\n    else return a.y < b.y ? 0 : 1;\r\n}\r\n\r\ninline int Rev(int dir){\r\n    return dir ^ 1;\r\n}\r\n\r\nvoid Insert(int &now = root, int level = 0){\r\n    if (!now) now = ++total, node[now] = temp;\r\n    else Insert(c[now][Dir(level, temp, node[now])], level + 1);\r\n}\r\n\r\nvoid Cut(int now, int parent, int level){\r\n    if (!now) return;\r\n\r\n    if (level&1){\r\n        if (node[now].x < node[parent].x) xl[now] = xl[parent], xr[now] = node[parent].x; else xl[now] = node[parent].x, xr[now] = xr[parent];\r\n        yl[now] = yl[parent], yr[now] = yr[parent];\r\n    }\r\n    else {\r\n        if (node[now].y < node[parent].y) yl[now] = yl[parent], yr[now] = node[parent].y; else yl[now] = node[parent].y, yr[now] = yr[parent];\r\n        xl[now] = xl[parent], xr[now] = xr[parent];\r\n    }\r\n\r\n\r\n    REP(i, 2) Cut(c[now][i], now, level + 1);\r\n}\r\n\r\nvoid Update(Rec item){\r\n\r\n    DB dd = dist_sqr(cur, item);\r\n\r\n    if (sgn(dd, d) <= 0){\r\n        if (sgn(dd, d) == -1) d = dd, CLR(L);\r\n        L.PB(item.id);\r\n    }\r\n}\r\n\r\nvoid Find(int now = root, int level = 0){\r\n\r\n    if (!now || sgn(d, ((xl[now] <= cur.x && cur.x <= xr[now]) ? 0. : min(sqr(cur.x - xl[now]), sqr(cur.x - xr[now]))) + ((yl[now] <= cur.y && cur.y <= yr[now]) ? 0. : min(sqr(cur.y - yl[now]), sqr(cur.y - yr[now])))) < 0) return;\r\n\r\n    int dir = Dir(level, cur, node[now]); Find(c[now][dir], level + 1), Update(node[now]); Find(c[now][Rev(dir)], level + 1);\r\n}\r\n\r\nint main() {\r\n\r\n    \/\/freopen("in.txt", "r", stdin);\r\n\r\n    REP_C(i, _RD(n)){\r\n        scanf("%lf %lf", &P[i].x, &P[i].y);\r\n        P[i].id = i + 1;\r\n    }\r\n\r\n    \/\/srand((unsigned)time(NULL)); REP(i, n) swap(P[i], P[random(i, n - 1)]);\r\n    REP(i, n) temp = P[i], Insert();\r\n\r\n    xl[root] = yl[root] = -10000, xr[root] = yr[root] = 10000;\r\n    REP(i, 2) Cut(c[root][i], root, 0);\r\n\r\n    DO_C(RD()){\r\n        scanf("%lf %lf", &cur.x, &cur.y), CLR(L), d = INF; Find();\r\n        SRT(L); REP(i, SZ(L) - 1) printf("%d ", L[i]);\r\n        printf("%d\\n", L[SZ(L)-1]);\r\n    }\r\n}\r\n<\/pre>\n
try\u795e\u7684\u4ee3\u7801<\/a><\/p>\n
Vonoir Graph: <\/h4>\n
Reference: <\/h3>\n
The Design and Analysis of Spatial Data Structures[Hanan][Samet]<\/a><\/p>\n
External links: <\/h3>\n
http:\/\/acm.timus.ru\/problem.aspx?space=1&num=1369<\/a>
\nhttp:\/\/en.wikipedia.org\/wiki\/Nearest_neighbor_search<\/a><\/p>\n","protected":false},"excerpt":{"rendered":"
Brief description: \u7ed9\u5b9a\u5e73\u9762\u4e0a\u7684\u4e00\u7ec4\u70b9\u96c6 \uff0c\u5bf9\u4e8e\u6bcf\u4e2a\u8be2\u95ee\uff0c\u8f93\u51fa\u4e00\u4e2a\u65b0\u7684\u70b9\uff0c\u67e5\u8be2\u6240\u6709\u8ddd\u79bb\u5979\u6700\u8fd1\u7684\u70b9\u7684\u7f16\u53f7\u3002 \uff08\u70b9\u96c6\u89c4\u6a21 N<\/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":[1],"tags":[24],"class_list":["post-13","post","type-post","status-publish","format-standard","hentry","category-uncategorized","tag-24"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/p2tdP7-d","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/13","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=13"}],"version-history":[{"count":1,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/13\/revisions"}],"predecessor-version":[{"id":14,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/13\/revisions\/14"}],"wp:attachment":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/media?parent=13"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/categories?post=13"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/tags?post=13"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}