#eFTPPlydlt60x6804. 蚂蚁 Ants
蚂蚁 Ants
好的,这是整理好的题面,不含解题思路,只包含样例解释。
题目描述
平面上共有 个点,其中 个白点, 个黑点。
对于每个白点,找到一个黑点,把二者用线段连起来,要求最后所有线段都不相交(允许端点重合,但坐标已给一般不同),求一种方案。
输入格式
第一行包含整数 。
接下来 行,每行两个整数,表示一个黑点的坐标。
再接下来 行,每行两个整数,表示一个白点的坐标。
输出格式
输出共 行,每行一个整数。
第 行的数,表示第 个黑点连接的白点的编号(白点的编号从 1 到 ,按输入顺序)。
注意答案可能不唯一,任意输出一种答案即可。
数据范围
- 坐标绝对值不超过
输入样例
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
样例解释
。
黑点坐标(编号 1 到 5):
- (-42,58)
- (44,86)
- (7,28)
- (99,34)
- (-13,-59)
白点坐标(编号 1 到 5):
- (-47,-44)
- (86,74)
- (68,-75)
- (-68,60)
- (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