ROCKETS - Rockets

no tags 

There are two separate, n-element sets of points of a two dimensional map: R and W. None triple of points from the set RUW is collinear. Rockets earth-to-earth are located on points from the set R. Enemy objects, which should be destroyed, are located on points from the set W. The rockets may fly only in the straight line and their trajectories cannot intersect. We are about to find for each rocket a target to destroy.


Write a program which:

  • reads from the standard input coordinates of the points from the sets R and W,
  • finds the set of n pairwise not-intersecting segments, so that one end of each segment belongs to the set R, while the other belongs to the set W,
  • writes the result into the standard output.


The number of test cases t is in the first line of input, then t test cases follow separated by an empty line. In the first line of each test case there is written one integer n, 1<=n<=10000, equal to the number of elements of the sets R and W.

In each of the following 2n lines of the input one pair of integer numbers from the interval [-10000, 10000] is written. Numbers in each pair are separated by a single space. They are coordinates of the point on a map (first coordinate x, then y). The first n lines comprise coordinates of the points from the set R, the last n lines comprise the points from the set W. In the (i+1)-th line there are coordinates of the point ri, in the (i+n+1)-th line there are coordinates of the point wi, 1<= i<= n.


The output for each test case should consist of n lines. In the i-th line there should be one integer k(i), such that the segment ri wk(i) belongs to the set of segments which your program found. (This means that the rocket from the point ri destroys an object in the point wk(i)).


Sample input:
0 0
1 5
4 2
2 6
1 2
5 4
4 5
3 1

Sample output:
Warning: large Input/Output data, be careful with certain languages

Added by:Piotr Ɓowiec
Time limit:1.200s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: NODEJS PERL6 VB.NET
Resource:6th Polish Olympiad in Informatics, stage 2