E3. Guard Duty (hard)

Codeforces

IDCF958E3

Time5000ms

Memory256MB

Difficulty—

geometry

English · Original

Chinese · Translation

Formal · Original

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: * The segments do not intersect. * Such a connection forms a perfect matching. ## Input The 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. ## Output The 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_. It is guaranteed that a solution exists. If there are multiple solutions, you can output any one of them. [samples]

现在 Heidi 已经知道她可以将叛军飞船分配到基地（回顾简单子任务），她想问你：究竟该如何精确地做到这一点？现在，给定平面上 #cf_span[N] 艘飞船和 #cf_span[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] 行格式相同，表示基地的位置。保证没有两个点重合，且没有三个点共线。输出应包含 #cf_span[N] 行。第 #cf_span[i] 行应包含一个整数 #cf_span[pi]，表示第 #cf_span[i] 艘飞船所连接的基地的编号。序列 #cf_span[p1, ..., pN] 应构成 #cf_span[1, ..., N] 的一个排列。保证存在解。如果存在多个解，你可以输出其中任意一个。 ## Input 第一行包含一个整数 #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] 行格式相同，表示基地的位置。保证没有两个点重合，且没有三个点共线。 ## Output 输出应包含 #cf_span[N] 行。第 #cf_span[i] 行应包含一个整数 #cf_span[pi]，表示第 #cf_span[i] 艘飞船所连接的基地的编号。序列 #cf_span[p1, ..., pN] 应构成 #cf_span[1, ..., N] 的一个排列。保证存在解。如果存在多个解，你可以输出其中任意一个。 [samples]

**Definitions** Let $ n \in \mathbb{Z} $, $ 1 \leq n \leq 10000 $. Let $ 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) $. Let $ 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') $. Assume all points in $ S \cup B $ are distinct and no three are collinear. **Constraints** 1. All coordinates satisfy $ |x_i|, |y_i|, |x_j'|, |y_j'| \leq 10000 $. 2. $ s_i \neq s_j $, $ b_i \neq b_j $, and $ s_i \neq b_j $ for all $ i \neq j $. 3. No three points from $ S \cup B $ are collinear. **Objective** Find 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. (Output any such permutation; existence is guaranteed.)

Samples

Input #1

Output #1

API Response (JSON)

{
  "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 pla...",
      "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_s...",
      "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 $ ...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments