P5936 [POI 1999 R2] Missiles

A war broke out between Country U and Country A.

The chief intelligence officer of Country U learned that Country A has already deployed $N$ strong bunkers along the border. The defense system formed by these bunkers will pose a huge threat to U's soldiers. Therefore, before launching an attack, U's Ministry of Defense must destroy these bunkers first. To achieve a surprise attack, the Ministry of Defense decided that each missile launch site on the border will be responsible for eliminating exactly one bunker. To catch the enemy off guard, the $N$ missile launch sites will fire at the same time. Each missile moves forward at full speed in a straight line, aiming to deliver a devastating strike to the bunker group in a short time. However, these missiles use ground-to-ground electronic guidance. If the flight paths of two missiles intersect, their electronic signals will interfere with each other, causing them to deviate from their intended targets. As a military advisor, you need to design an operation plan: decide in advance which bunker each missile launch site will attack, and make sure that under your plan, the missile flight paths do not intersect. The intelligence department has clearly marked the positions of the missile launch sites and the bunkers on the map, and guarantees that among these $2N$ points, no three points are collinear.

The first line contains an integer $N$, the number of missile launch sites, which is also the number of enemy bunkers. The next $N$ lines each contain two integers $Rx_i$ and $Ry_i\ (0\le |Rx_i|,|Ry_i|\le 10^4)$. Line $i+1$ gives the coordinates of the $i$-th missile launch site. The following $N$ lines each contain two integers $Wx_i$ and $Wy_i\ (0\le |Wx_i|,|Wy_i|\le 10^4)$. Line $N+i+1$ gives the coordinates of the $i$-th bunker.

Output $N$ lines. The $i$-th line contains an integer $P_i$, meaning that the $i$-th missile launch site is responsible for destroying the $P_i$-th bunker.

For $100\%$ of the testdata, $1\le N\le 10000$. Translated by ChatGPT 5