飞弹

Grade 0 Open Time Thursday, 21 February 2013, 11:02 pm
Discount 0.8 Time Discount Thursday, 28 February 2013, 11:02 pm
Allow late Yes Close Time Thursday, 28 February 2013, 11:02 pm
Input file rak.in Output file rak.out

问题描述

一场战争在 U 国与 A 国之间爆发了。 U 国的负责情报的长官得知, A 国在边界上已经事先布置了 N 个坚实的地堡,这些地堡组成的防御体系将对 U 国的士兵构成极大的威胁! U 国国防部不得不在进攻之前先摧毁这些地堡!

为了出奇制胜, U 国国防部决定:布置在边界的每一个飞弹发射点负责消灭一个地堡。为了给敌人一个措手不及, N 个飞弹发射点将同时发射飞弹,每个飞弹均以直线全速前进,争取在短时间内给地堡群造成毁灭性的打击。

但是,由于这些飞弹是地对地电子制导型的,两颗飞弹的飞行路线如果相交,电子信号将会互相干扰,从而偏离预定目标。

作为军事顾问,国防部需要你来设计一个作战方案,事先确定每个飞弹点负责哪一个地堡,并且在所设计的方案中,飞弹的飞行线路不相交。

情报部门已经将飞弹发射点和地堡的位置明确标在地图上,并保证这 2N 个坐标点不存在三点共线。


输入文件

输入文件名: rak.in

第一行是一个数 N ( 1<=N<=10000 ),表示飞弹发射点的个数,也是敌方地堡的个数。

以下 N 行,每行两个整数 x 和 y (在 [-10000,10000] 内),第 i+1 行表示第 i 个飞弹发射点的坐标,。

再下面 N 行,每行两个整数 x 和 y (在 [-10000,10000] 内),第 N+i+1 行表示第 i 个地堡的坐标。


输出文件

输出文件名: rak.out

输出文件有 N 行,每行为一个整数。第 i 行的整数 P i 表示,第 i 个飞弹发射点负责消灭第 P i 个地堡。


样例输入
4
0 0
1 5
4 2
2 6
1 2
5 4
4 5
3 1

样例输出
2
1
4
3