Non‐Intersecting Missile Targeting

In country U, intelligence has reported that country A has set up N impregnable bunkers along the border. To disable them before the attack, U plans to fire N missiles simultaneously from N missile launching points situated on the border. Each missile is responsible for destroying one bunker. However, because the missiles use ground-to‐ground electronic guidance, if any two missile trajectories (which are straight lines) intersect, their electronic signals interfere causing them to miss their targets.

Your task is to design an operation plan to assign each missile launching point to one bunker so that the straight-line paths connecting them are pairwise non–intersecting. It is known that the positions of the missile launching points and bunkers are given as coordinates, and the total of 2 × N points are in general position (i.e. no three points are collinear).

Note: A valid solution always exists. One way to guarantee non–intersection is to pair the points according to their order along the convex polygon formed by the given points. In our solution, assume that the points, though given in arbitrary order, lie on the boundary of a convex region.

More formally, let each missile point be denoted by a coordinate \( (x_i, y_i) \) for \( i=1,2,\dots,N \) and each bunker point by \( (x_j, y_j) \) for \( j=1,2,\dots,N \). We want to find a bijection \( f:\{1,2,\dots,N\}\to\{1,2,\dots,N\} \) so that the segments connecting \( (x_i, y_i) \) to \( (x_{f(i)}, y_{f(i)}) \) (for missile and bunker respectively) do not intersect.

A hint for one approach: compute the center of mass of all 2N points and sort the points by their polar angle with respect to this center. Then, apply a standard DP or recursive matching algorithm to pair the points in a way that maintains non–intersection.

inputFormat

The first line contains an integer N (\(1 \le N \le \text{small}\)) indicating the number of missile launching points (and also the number of bunkers).
The following N lines each contain two real numbers representing the coordinates of the missile launching points.
The next N lines each contain two real numbers representing the coordinates of the bunkers.

outputFormat

Output N lines. The ith line should contain a single integer representing the 1-indexed bunker assigned to the ith missile (in the input order).

sample

1
0 0
0 1

1