#eFTPPlydlt60x6804. 蚂蚁 Ants

蚂蚁 Ants

好的,这是整理好的题面,不含解题思路,只包含样例解释。


题目描述

平面上共有 2×N2\times N 个点,其中 NN 个白点,NN 个黑点。
对于每个白点,找到一个黑点,把二者用线段连起来,要求最后所有线段都不相交(允许端点重合,但坐标已给一般不同),求一种方案。


输入格式

第一行包含整数 NN
接下来 NN 行,每行两个整数,表示一个黑点的坐标。
再接下来 NN 行,每行两个整数,表示一个白点的坐标。

输出格式

输出共 NN 行,每行一个整数。
ii 行的数,表示第 ii 个黑点连接的白点的编号(白点的编号从 1 到 NN,按输入顺序)。

注意答案可能不唯一,任意输出一种答案即可。

数据范围

  • 1N1001 \le N \le 100
  • 坐标绝对值不超过 1000010000

输入样例

5
-42 58
44 86
7 28
99 34
-13 -59
-47 -44
86 74
68 -75
-68 60
99 -60

输出样例

4
2
1
5
3

样例解释

N=5N=5

黑点坐标(编号 1 到 5):

  1. (-42,58)
  2. (44,86)
  3. (7,28)
  4. (99,34)
  5. (-13,-59)

白点坐标(编号 1 到 5):

  1. (-47,-44)
  2. (86,74)
  3. (68,-75)
  4. (-68,60)
  5. (99,-60)

输出含义

第 1 行:4 表示黑点 1 连白点 4
第 2 行:2 表示黑点 2 连白点 2
第 3 行:1 表示黑点 3 连白点 1
第 4 行:5 表示黑点 4 连白点 5
第 5 行:3 表示黑点 5 连白点 3

这样形成 5 条线段,互不相交(可以根据坐标画图验证)。


输出

4
2
1
5
3