Коровы Фермера Джона любят производить лазерные шоу.
Для своего последнего шоу, они купили огромный мощный лазер - такой большой,
что они не смогли перместить его легко из того места, где он был приобретен.
Он хотят послать свет от лазера в амбар ФД. И лазер, и амбра могут рассматриваться
как точки на плоскости - карте фермы ФД. В панах коров направить лазер так,
чтобы он послал лч света горизонтально или вертикально (то есть вдоль оси x или
вдоль оси y). Затем они планируют ментяь направление луча посредством зеркал,
чтобы направить луч в амбар.
На этой ферме есть \(N\) (\(1 \leq N \leq 100,000\)) точек изгороди, расположенных
в различных точках на плоскости, (и отличающихся также от точек лазера и амбара),
на которых могут крепится зеркала. Коровы могут выбрать не крепить зеркало к
некоторым точкам, тогда луч просто проходит через эту точку без поворотов (не меняя
направление). Если коровы монтируют зеркало в точке изгороди, они выравнивают его
диагонально так / или так \, что соответсвенно пернаправляет горизонтальный в
вертикальный и наоборот.
Вычислите минимально возможное количество зеркал, которое необходимо коровам,
чтобы пернаправить лазер в амбар.
ФОРМАТ ВВОДА (файл lasers.in):
Первая строка ввода содержит 5 целых чисел, разделённых одиночными пробелами.
\(N, x_L, y_L, x_B, y_B\), где
\((x_L, y_L)\) - это размещение лазера,
\((x_B, y_B)\) -
размещение амбара. Все координаты между
\(0\) и
\(1,000,000,000\).
Каждая из следующих \(N\) строк содержит \(x\) и \(y\) - координаты точек изгороди
- целые числа в интервале \(0 \ldots 1,000,000,000\).
ФОРМАТ ВЫВОДА (файл lasers.out):
Выведите минимальное колчиество зеркал, которое необходимо чтобы перенаправить
лазер в амбар, или -1, если это невозможно сделать.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4 0 0 7 2
3 2
0 2
1 6
3 0
|
1
|