:-/Problem 2: Connect the Cows [Brian Dean, 2012]
Каждый день Фермер Джон обходит свою ферму, чтобы проведать N
(1 <= N <= 10) своих коров.
Местоположение каждой из его коров описывается точкой на координатной
плоскости, а ФД начинает в точке (0,0). Чтобы сделать маршрут более
интересным, ФД ходит только параллельно осям координат (на север, юг,
восток и запад). Он меняет направление своего движения, только когда он
добирается до одной из коров. Если пожелает, он может не менять
направление своего движения, проходя через местоположение коровы.
Когда ФД меняет направление движения, он может менять его на 90 или 180
градусов. ФД должен вернутся в исходную точку после посещения всех
коров.
Пожалуйста, вычислите общее количество способов, которыми ФД может
посетить всех своих коров, если он изменит направление своего движения
ровно один раз у каждой коровы. Не изменяя направление движения, он
может ходить мимо коровы произвольное количество раз. Один и тот же
геометрический путь, пройденный в прямом и обратном направлениях,
считается как два различных маршрута.
PROBLEM NAME: connect
INPUT FORMAT:
* Строка 1: Целое число N.
* Строки 2..1+N: Строка i+1 содержит x и y координаты (разделенные пробелом)
для i-ой точки(все числа в диапазоне -1000...1000).
SAMPLE INPUT (файл connect.in):
4
0 1
2 1
2 0
2 -5
INPUT DETAILS:
Всего 4 коровы, в позициях (0,1), (2,1), (2,0), (2,-5).
OUTPUT FORMAT:
* Строка 1: Количество различных маршрутов ФД
(может быть равным 0, если их нет)
SAMPLE OUTPUT (файл connect.out):
2
OUTPUT DETAILS:
Всего есть два различных маршрута
1-2-4-3 или 3-4-2-1
прежде чем ФД вернется в точку (0,0).
Language:
