Строгий Город
Однажды Вася настолько устал, решая задачи по геометрии, что уснул прямо за тетрадкой в процессе решения очередной задачи. Ему приснилось, что он попал в город Строгий, в котором всё подчинялось строгим законам. В городе была введена система координат, а все дороги были либо строго вертикальными (параллельными оси OY), либо строго горизонтальными (параллельными оси OX). Точки пересечения вертикальных дорог с горизонтальными дорогами образовывали перекрестки. Все дороги в Строгом односторонние — перемещаться по каждой из них можно лишь в одном направлении, а перемещаться не по дорогам строго запрещено.
Во сне перед Васей постоянно вставала задача — насколько быстро можно добраться из одного перекрестка города в другой и можно ли это сделать вообще? На каждую такую задачу Вася должен был дать точный ответ, в противном случае он был бы строго наказан. Помогите Васе! По конфигурации дорог города для каждого запроса нужно определить наименьшее расстояние, которое придется преодолеть, чтобы попасть из начального перекрестка в конечный, не нарушая правил перемещения по городу.
В первой строке заданы три целых числа — V, H, Q — количество вертикальных дорог в городе, количество горизонтальных дорог в городе и количество запросов (1 ≤ V, H, Q ≤ 50 000).
В каждой из следующих V строк описывается одна вертикальная дорога. Дорога задается двумя целыми числами Xi и Ti — координатой пересечения с осью OX и направлением ( - 109 ≤ Xi ≤ 109, Ti = 1 или Ti = - 1). Если Ti равно 1, то по дороге можно двигаться в сторону увеличения координаты, если Ti равно - 1 — в сторону уменьшения. Все Xi различны и указаны строго в порядке возрастания.
В следующих H строках описаны горизонтальные дороги в том же формате. Аналогично, горизонтальные дороги перечислены в порядке возрастания Yi — координаты пересечения с осью OY.
В каждой из следующих Q строк содержится по одному запросу. Запрос задается четырьмя целыми числами Xa, Ya, Xb, Yb — координатами начальной точки и конечной точки соответственно. Гарантируется, что как начальная, так и конечная точки являются перекрестками, то есть лежат на пересечении вертикальной и горизонтальной дорог.
Для каждого запроса необходимо вывести единственное число — минимальное расстояние, которое придется преодолеть по дорогам города, чтобы попасть из начальной точки в конечную. Если этого сделать невозможно, не нарушая правил движения, нужно вывести - 1. Ответы на запросы следует разделять пробелами или переводами строк.
В тестах общей стоимостью 30 баллов координаты дорог не будут превосходить 50 по абсолютному значению, количество запросов также не будет превышать 50.
В тестах общей стоимостью 60 баллов количество вертикальных дорог, горизонтальных дорог и количество запросов не будет превышать 50.
2 2 4
0 -1
2 -1
0 -1
1 1
2 1 2 0
2 0 0 0
2 1 0 0
0 0 2 1
1
2
3
-1
Задача на Codeforces (контест gym/102112, задача A, © Codeforces.com)