Лазеры и зеркала
Лазеры и зеркала
Коровы Фермера Джона любят производить лазерные шоу.
Для своего последнего шоу, они купили огромный мощный лазер - такой большой, что они не смогли перместить его легко из того места, где он был приобретен. Он хотят послать свет от лазера в амбар ФД. И лазер, и амбра могут рассматриваться как точки на плоскости - карте фермы ФД. В панах коров направить лазер так, чтобы он послал лч света горизонтально или вертикально (то есть вдоль оси x или вдоль оси y). Затем они планируют ментяь направление луча посредством зеркал, чтобы направить луч в амбар.
На этой ферме есть n точек изгороди, расположенных в различных точках на плоскости, (и отличающихся также от точек лазера и амбара), на которых могут крепится зеркала. Коровы могут выбрать не крепить зеркало к некоторым точкам, тогда луч просто проходит через эту точку без поворотов (не меняя направление). Если коровы монтируют зеркало в точке изгороди, они выравнивают его диагонально так / или так \, что соответсвенно пернаправляет горизонтальный в вертикальный и наоборот.
Вычислите минимально возможное количество зеркал, которое необходимо коровам, чтобы пернаправить лазер в амбар.
Входные данные
Первая строка содержит 5 целых чисел n (1 ≤ n ≤ 105
), xl
, yl
, xb
, yb
, где (xl
, yl
) - это размещение лазера, (xb
, yb
) - размещение амбара. Все координаты между 0 и 109
.
Каждая из следующих n строк содержит x и y - координаты точек изгороди - целые числа в интервале 0 .. 109
.
Выходные данные
Выведите минимальное колчиество зеркал, которое необходимо чтобы перенаправить лазер в амбар, или -1, если это невозможно сделать.
4 0 0 7 2 3 2 0 2 1 6 3 0
1