eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Муравьи

Муравьи

Ліміт часу 1 секунда
Ліміт використання пам'яті 128 MiB

Юный натуралист Билл изучает в школе муравьёв. Его муравьи питаются растительными вшами, которые живут на яблонях. Каждая колония муравьев нуждается в своей собственной яблони чтобы прокормить себя.

Билл имеет карту с координатами n колоний муравьев и n яблонь. Он знает, что муравьи двигаются со своей колонии до мест питания и обратно, используя химически маркированные маршруты. Маршруты не могут пересекаться, в этом случае другие муравьи могут запутаться и получить доступ к дереву другой колонии, тем самым стимулируя войну между колониями.

Билл хотел бы соединить каждую колонию муравьев с одной яблоней так, чтобы все n маршрутов являлись непересекающимися прямыми линиями. В этой задаче такое соединение всегда возможно. Вам следует написать программу, которая найдет такое соединение.

prb7584.gif

На картинке колонии муравьев обозначены пустыми кружками, яблони обозначены закрашенными кругами. Одно из возможных соединений обозначено линиями.

Вхідні дані

Первая строка содержит число n (1n100) - количество колоний муравьев и яблонь. Далее следуют n строк описывающих n муравьиных колоний, за которыми следуют n строк описывающих n яблонь. Каждая колония муравьев и яблоня задается парой целочисленных координат x и y (-10 000x, y10 000) в декартовой системе координат. Все колонии муравьев и яблони занимают различные точки на плоскости. Никакие три точки не находятся на одной линии.

Вихідні дані

Вывести n чисел, по одному в каждой строке. Число, записанное в i-ой строке, указывает на номер яблони(от 1 до n), которая будет соединена с i-ой колонией.

Приклад

Вхідні дані #1
5
-42 58
44 86
7 28
99 34
-13 -59
-47 -44
86 74
68 -75
-68 60
99 -60
Вихідні дані #1
4
2
3
5
1
Джерело 2007 ACM NEERC, Semifinals, November 28, Problem A