{"raw_statement":[{"iden":"statement","content":"The stardate is 2015, and Death Stars are bigger than ever! This time, two rebel spies have yet again given Heidi two maps with the possible locations of the Death Stars.\n\nHeidi has now received two maps with possible locations of _N_ Death Stars. She knows that each of the maps is possibly corrupted, and may contain some stars that are not Death Stars. Furthermore, each of the maps was created from a different point of view. Hence, stars that are shown in one of the maps are rotated and translated with respect to the other map. Now Heidi wants to find out which of the stars shown in both maps are actually Death Stars, and the correspondence between the Death Stars on the two maps."},{"iden":"input","content":"The first line of the input contains an integer _N_ (1000 ≤ _N_ ≤ 50000) – the number of Death Stars. The second line of the input contains an integer _N_1 (_N_ ≤ _N_1 ≤ 1.5·_N_) – the number of stars in the first map. The next _N_1 lines specify the coordinates of the stars in the first map. The _i_\\-th line contains two space-separated floating-point numbers _x__i_ and _y__i_ with two decimal digits of precision each, representing the coordinates of the _i_\\-th star in the first map.\n\nThe next line of the input contains an integer _N_2 (_N_ ≤ _N_2 ≤ 1.5·_N_) – the number of stars in the second map. The next _N_2 lines contain locations of the stars in the second map, given in the same format as for the first map."},{"iden":"output","content":"You should output exactly _N_ lines, each containing a space-separated pair of integers _i_1 and _i_2. Each such line should indicate that the star numbered _i_1 in the first map corresponds to the star numbered _i_2 in the second map. Your answer will be considered correct if over 90% of the distinct pairs listed in your output are indeed correct."},{"iden":"note","content":"The tests are generated in the following way:\n\n*   The number of Death Stars _N_ is pre-selected in some way.\n*   The numbers of stars on the first and on the second map, _N_1 and _N_2, are selected uniformly at random between 1.0 × _N_ and 1.5 × _N_.\n*   _N_ Death Stars are generated at random, with coordinates between  - 10000 and 10000.\n*   Additional _N_1 - _N_ and _N_2 - _N_ stars for the first and for the second map respectively are generated in the same way.\n*   A translation vector (_dx_, _dy_) is generated, with _dx_ and _dy_ selected uniformly at random between  - 10000 and 10000. Each point in the first map is translated by (_dx_, _dy_).\n*   A rotation angle θ is generated, with θ selected uniformly at random between 0 and 2π. Each point in the first map is rotated by an angle of θ around the origin.\n*   Translations and rotations for the second map are generated and applied in the same way.\n*   The order of points is randomly permuted for both maps.\n*   The test case is saved, with each point written with two decimal digits of precision."}],"translated_statement":[{"iden":"statement","content":"星历为2015年，死星比以往任何时候都更大！这一次，两名反抗军间谍再次给了海蒂两张可能包含死星位置的地图。\n\n海蒂现在收到了两张地图，分别列出了 #cf_span[N] 颗死星的可能位置。她知道每张地图都可能被污染，包含一些并非死星的恒星。此外，每张地图是从不同的视角创建的，因此一张地图中的恒星相对于另一张地图经过了旋转和平移。现在海蒂希望找出两张地图中共同出现的恒星中哪些实际上是死星，以及两张地图中死星之间的对应关系。\n\n输入的第一行包含一个整数 #cf_span[N] (#cf_span[1000 ≤ N ≤ 50000]) —— 死星的数量。第二行包含一个整数 #cf_span[N1] (#cf_span[N ≤ N1 ≤ 1.5·N]) —— 第一张地图中恒星的数量。接下来的 #cf_span[N1] 行指定第一张地图中恒星的坐标，第 #cf_span[i] 行包含两个用空格分隔的浮点数 #cf_span[xi] 和 #cf_span[yi]，精确到两位小数，表示第一张地图中第 #cf_span[i] 颗恒星的坐标。\n\n接下来的一行包含一个整数 #cf_span[N2] (#cf_span[N ≤ N2 ≤ 1.5·N]) —— 第二张地图中恒星的数量。接下来的 #cf_span[N2] 行以与第一张地图相同的格式给出第二张地图中恒星的位置。\n\n你应该输出恰好 #cf_span[N] 行，每行包含一对用空格分隔的整数 #cf_span[i1] 和 #cf_span[i2]。每行应表示第一张地图中编号为 #cf_span[i1] 的恒星对应于第二张地图中编号为 #cf_span[i2] 的恒星。如果你输出的 distinct 对中超过 90% 是正确的，则你的答案将被视为正确。\n\n测试用例按以下方式生成：\n\n"},{"iden":"input","content":"输入的第一行包含一个整数 #cf_span[N] (#cf_span[1000 ≤ N ≤ 50000]) —— 死星的数量。第二行包含一个整数 #cf_span[N1] (#cf_span[N ≤ N1 ≤ 1.5·N]) —— 第一张地图中恒星的数量。接下来的 #cf_span[N1] 行指定第一张地图中恒星的坐标，第 #cf_span[i] 行包含两个用空格分隔的浮点数 #cf_span[xi] 和 #cf_span[yi]，精确到两位小数，表示第一张地图中第 #cf_span[i] 颗恒星的坐标。接下来的一行包含一个整数 #cf_span[N2] (#cf_span[N ≤ N2 ≤ 1.5·N]) —— 第二张地图中恒星的数量。接下来的 #cf_span[N2] 行以与第一张地图相同的格式给出第二张地图中恒星的位置。"},{"iden":"output","content":"你应该输出恰好 #cf_span[N] 行，每行包含一对用空格分隔的整数 #cf_span[i1] 和 #cf_span[i2]。每行应表示第一张地图中编号为 #cf_span[i1] 的恒星对应于第二张地图中编号为 #cf_span[i2] 的恒星。如果你输出的 distinct 对中超过 90% 是正确的，则你的答案将被视为正确。"},{"iden":"note","content":"测试用例按以下方式生成：\n\n死星的数量 #cf_span[N] 以某种方式预先选定。\n第一张和第二张地图中恒星的数量 #cf_span[N1] 和 #cf_span[N2] 在 #cf_span[1.0 × N] 到 #cf_span[1.5 × N] 之间均匀随机选取。\n在 #cf_span[ - 10000] 到 #cf_span[10000] 范围内随机生成 #cf_span[N] 颗死星的坐标。\n为第一张和第二张地图分别额外生成 #cf_span[N1 - N] 和 #cf_span[N2 - N] 颗恒星，生成方式相同。\n生成一个平移向量 #cf_span[(dx, dy)]，其中 #cf_span[dx] 和 #cf_span[dy] 在 #cf_span[ - 10000] 到 #cf_span[10000] 之间均匀随机选取。第一张地图中的每个点都按 #cf_span[(dx, dy)] 平移。\n生成一个旋转角度 #cf_span[θ]，其中 #cf_span[θ] 在 #cf_span[0] 到 #cf_span[2π] 之间均匀随机选取。第一张地图中的每个点都绕原点旋转角度 #cf_span[θ]。\n第二张地图的平移和旋转以相同方式生成并应用。\n两张地图中的点顺序被随机打乱。\n测试用例被保存，每个点以两位小数的精度写出。"}],"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ N \\in \\mathbb{Z} $ be the true number of Death Stars, with $ 1000 \\leq N \\leq 50000 $.  \nLet $ N_1 \\in \\mathbb{Z} $ be the number of stars in Map 1, with $ N \\leq N_1 \\leq 1.5N $.  \nLet $ N_2 \\in \\mathbb{Z} $ be the number of stars in Map 2, with $ N \\leq N_2 \\leq 1.5N $.  \n\nLet $ M_1 = \\{ p_{1,1}, p_{1,2}, \\dots, p_{1,N_1} \\} \\subset \\mathbb{R}^2 $ be the set of star coordinates in Map 1, where $ p_{1,i} = (x_{1,i}, y_{1,i}) $.  \nLet $ M_2 = \\{ p_{2,1}, p_{2,2}, \\dots, p_{2,N_2} \\} \\subset \\mathbb{R}^2 $ be the set of star coordinates in Map 2, where $ p_{2,j} = (x_{2,j}, y_{2,j}) $.  \n\nLet $ D_1 \\subset M_1 $ and $ D_2 \\subset M_2 $ be the subsets of size $ N $ corresponding to the true Death Stars in each map.  \nThere exists an unknown rigid transformation $ T: \\mathbb{R}^2 \\to \\mathbb{R}^2 $ (i.e., composition of rotation and translation) such that $ T(D_1) = D_2 $.\n\n**Constraints**  \n1. $ 1000 \\leq N \\leq 50000 $  \n2. $ N \\leq N_1 \\leq 1.5N $  \n3. $ N \\leq N_2 \\leq 1.5N $  \n4. All coordinates are given with two decimal digits of precision.  \n5. The true Death Stars in Map 1 are mapped bijectively to those in Map 2 via a rigid transformation $ T $.  \n6. $ M_1 \\setminus D_1 $ and $ M_2 \\setminus D_2 $ contain noise (non-Death Star stars), not related by $ T $.\n\n**Objective**  \nFind a bijection $ f: \\{1, \\dots, N\\} \\to \\{1, \\dots, N\\} $ such that for $ N $ correctly matched Death Star pairs,  \n$$\nT(p_{1, i_k}) = p_{2, j_k} \\quad \\text{for } k = 1, \\dots, N\n$$  \nand output $ N $ pairs $ (i_k, j_k) $, where $ i_k $ is the index in Map 1 and $ j_k $ is the index in Map 2 of the $ k $-th matched Death Star.  \n\nThe solution is accepted if at least 90% of the output pairs are correct.","simple_statement":null,"has_page_source":false}