TLE '17 Contest 7 P5 - Willson and Mating

View as PDF

Submit solution

Points: 15 (partial)
Time limit: 1.0s
Memory limit: 256M

Problem type
Willson in a field with other geese. One of the others is his mate.

Willson the Canada Goose is like any other Canada Goose - he chooses a mate and sticks with her for life.

Willson and his extended family land in a large grass field after migrating back from California. There are N male geese and N female geese. The i^{th} male goose is located at (x_{i1},y_{i1}) and the j^{th} female goose is located at (x_{j2},y_{j2}).

As a wildlife observer, you know that mating geese pairs will try to stay as close together as possible. You wonder to yourself what the mating pairs are. You do this by partitioning the geese into pairs consisting of one male goose and one female goose. Additionally, the total distance between the geese of each pair should be minimal. Can you produce such a partition?


1 \le N \le 100, all coordinates c satisfy |c| \le 100.

110N \le 8
220N \le 18
370No additional constraints.

Input Specification

The first line of input will contain N, the number of male geese and female geese.

N lines of input follow. The i^{th} line will contain integers x_{i1} and y_{i1}, the position of the i^{th} male goose.

N more lines of input follow. The j^{th} line will contain integers x_{j2} and y_{j2}, the position of the j^{th} female goose.

Output Specification

Output N lines, your partition of geese. Each line should contain two integers, i and j, signifying that the i^{th} male goose is paired with the j^{th} female goose. You may output in any order and output any solution with minimal total distance. Your answer will be judged as correct if your total distance has an absolute or relative error of no more than 10^{-8}.

Sample Input

0 0
1 0
1 1
0 1

Sample Output

1 2
2 1

Explanation for Sample Output

The distance between geese in each pair is 1, so the total distance is 2. The other possible pairing gives a total distance of 2\sqrt{2}.


There are no comments at the moment.