print2145. Дороги

printДороги

Ограничения: время – 2s/4s, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

Дорожная сеть города Нью-Флетсити устроена довольно просто. Все дороги являются отрезками единичной длины с концами в точках с целыми координатами. Этот факт – своего рода достопримечательность Нью-Флетсити.
Недавно пришедший к власти мэр считает, что он тратит слишком много времени на дорогу из дома в мэрию и обратно. Он решил построить несколько новых дорог так, чтобы этот путь был как можно короче. Естественно, новые дороги должны также являться единичными отрезками с концами в целых точках.
Вам, как главному инженеру Нью-Флетсити, поручено вычислить минимальное количество дорог, которое придется построить для осуществления плана мэра.
Первая строка входного файла содержит целое число `n` – количество дорог в Нью-Флетсити (`0\ ≤\ n\ ≤\ 100`). Далее следуют `n` строк с четырьмя целыми числами, разделенными пробелами: `x_i,\ y_i,\ x_j,\ y_j` – координаты начала и конца соответствующей дороги (`0\ ≤\ x_i,\ y_i,\ x_j,\ y_j\ ≤\ 100`). Последняя строка содержит два целых числа `m_x` и `m_y` – координаты дома мэра (`0\ ≤\ m_x,\ m_y\ ≤\ 100`). Мэрия расположена в точке `(0,\ 0)`.
Все дороги расположены либо по горизонтали, либо по вертикали, а длина каждой из этих дорог равна единице. Движение по дорогам возможно в обе стороны.
В выходной файл на первой строке выведите число `M` – количество новых дорог, которые нужно построить в Нью-Флетсити.

Пример ввода 1

1
0 0 1 0
1 1

Пример вывода 1

1

Пример ввода 2

5
0 0 1 0
1 0 1 1
1 1 0 1
0 1 0 2
0 2 1 2
1 2

Пример вывода 2

1
Источник: neerc.ifmo.ru/school
loading