← 返回题目列表

Codeforces · 958/E3

E3. 警卫职责(硬)

中文机器翻译题面 查看原题

现在海蒂知道她可以将义军太空飞船分配给基地(回想一下简单的子任务),她问你:到底该怎么做?现在,给定平面上 N 艘宇宙飞船和 N 个基地的位置,你的任务是用线段连接宇宙飞船和基地,以便:

- 线段不相交。
- 这样的连接形成了完美的匹配。

输入

第一行包含一个整数 N (1 ≤ n ≤ 10000)。对于 1 ≤ i ≤ N,第 i + 1 行包含两个整数 xi 和 yi (|xi|, |yi| ≤ 10000),表示第 i 艘飞船的坐标。接下来的N行具有相同的格式,表示碱基的位置。保证没有两点重合,也没有三点在同一条直线上。

输出

输出应有 N 行。第 i 行应包含一个整数 pi,即第 i 艘飞船所连接的基座的索引。序列 p1, ..., pN 应形成 1, ..., N 的排列。

保证存在解。如果有多个解,可以输出其中任意一个。

示例

输入 #1

4
6 6
5 1
2 4
4 0
5 4
1 2
2 1
3 5

输出 #1

4
1
2
3