{"problem":{"name":"E3. Guard Duty (hard)","description":{"content":"Now that Heidi knows that she can assign Rebel spaceships to bases (recall the easy subtask), she is asking you: how _exactly_ to do this? Now, given positions of _N_ spaceships and _N_ bases on a pla","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":5000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF958E3"},"statements":[{"statement_type":"Markdown","content":"Now that Heidi knows that she can assign Rebel spaceships to bases (recall the easy subtask), she is asking you: how _exactly_ to do this? Now, given positions of _N_ spaceships and _N_ bases on a plane, your task is to connect spaceships and bases with line segments so that:\n\n*   The segments do not intersect.\n*   Such a connection forms a perfect matching.\n\n## Input\n\nThe first line contains an integer _N_ (1 ≤ _n_ ≤ 10000). For 1 ≤ _i_ ≤ _N_, the _i_ + 1\\-th line contains two integers _x__i_ and _y__i_ (|_x__i_|, |_y__i_| ≤ 10000) denoting the coordinates of the _i_\\-th spaceship. The following _N_ lines have the same format, denoting the position of bases. It is guaranteed that no two points coincide and no three points are on the same line.\n\n## Output\n\nThe output should have _N_ lines. The _i_\\-th line should contain an integer _p__i_, the index of the base to which the _i_\\-th spaceship is connected. The sequence _p_1, ..., _p__N_ should form a permutation of 1, ..., _N_.\n\nIt is guaranteed that a solution exists. If there are multiple solutions, you can output any one of them.\n\n[samples]","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"现在 Heidi 已经知道她可以将叛军飞船分配到基地（回顾简单子任务），她想问你：究竟该如何精确地做到这一点？现在，给定平面上 #cf_span[N] 艘飞船和 #cf_span[N] 个基地的位置，你的任务是用线段将飞船与基地连接，使得：\n\n第一行包含一个整数 #cf_span[N] (#cf_span[1 ≤ n ≤ 10000])。对于 #cf_span[1 ≤ i ≤ N]，第 #cf_span[i + 1] 行包含两个整数 #cf_span[xi] 和 #cf_span[yi] (#cf_span[|xi|, |yi| ≤ 10000])，表示第 #cf_span[i] 艘飞船的坐标。接下来的 #cf_span[N] 行格式相同，表示基地的位置。保证没有两个点重合，且没有三个点共线。\n\n输出应包含 #cf_span[N] 行。第 #cf_span[i] 行应包含一个整数 #cf_span[pi]，表示第 #cf_span[i] 艘飞船所连接的基地的编号。序列 #cf_span[p1, ..., pN] 应构成 #cf_span[1, ..., N] 的一个排列。\n\n保证存在解。如果存在多个解，你可以输出其中任意一个。\n\n## Input\n\n第一行包含一个整数 #cf_span[N] (#cf_span[1 ≤ n ≤ 10000])。对于 #cf_span[1 ≤ i ≤ N]，第 #cf_span[i + 1] 行包含两个整数 #cf_span[xi] 和 #cf_span[yi] (#cf_span[|xi|, |yi| ≤ 10000])，表示第 #cf_span[i] 艘飞船的坐标。接下来的 #cf_span[N] 行格式相同，表示基地的位置。保证没有两个点重合，且没有三个点共线。\n\n## Output\n\n输出应包含 #cf_span[N] 行。第 #cf_span[i] 行应包含一个整数 #cf_span[pi]，表示第 #cf_span[i] 艘飞船所连接的基地的编号。序列 #cf_span[p1, ..., pN] 应构成 #cf_span[1, ..., N] 的一个排列。保证存在解。如果存在多个解，你可以输出其中任意一个。\n\n[samples]","is_translate":true,"language":"Chinese"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ n \\in \\mathbb{Z} $, $ 1 \\leq n \\leq 10000 $.  \nLet $ S = \\{s_1, s_2, \\dots, s_n\\} \\subset \\mathbb{R}^2 $ be the set of spaceship positions, where $ s_i = (x_i, y_i) $.  \nLet $ B = \\{b_1, b_2, \\dots, b_n\\} \\subset \\mathbb{R}^2 $ be the set of base positions, where $ b_j = (x_j', y_j') $.  \nAssume all points in $ S \\cup B $ are distinct and no three are collinear.\n\n**Constraints**  \n1. All coordinates satisfy $ |x_i|, |y_i|, |x_j'|, |y_j'| \\leq 10000 $.  \n2. $ s_i \\neq s_j $, $ b_i \\neq b_j $, and $ s_i \\neq b_j $ for all $ i \\neq j $.  \n3. No three points from $ S \\cup B $ are collinear.\n\n**Objective**  \nFind a permutation $ p = (p_1, p_2, \\dots, p_n) \\in S_n $ such that the mapping $ s_i \\mapsto b_{p_i} $ is a bijection between spaceships and bases.  \n(Output any such permutation; existence is guaranteed.)","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF958E3","tags":["geometry"],"sample_group":[["4\n6 6\n5 1\n2 4\n4 0\n5 4\n1 2\n2 1\n3 5","4\n1\n2\n3"]],"created_at":"2026-03-03 11:00:39"}}