|
Дом Мэра
(Время: 5 сек. Память: 16 Мб Сложность: 74%)
При планировании нового района города М было решено, что дороги в новом районе будут образовывать прямоугольную сетку, то есть все улицы будут одного из двух типов – направленные с юга на север или направленные с востока на запад. При этом параллельные улицы будут проходить через каждый километр, и каждый квартал будет иметь размер ровно один километр на один километр. Таким образом, все дороги образуют равномерную клетчатую сетку. По каждой дороге разрешен проезд в любом из двух направлений.
Через некоторое время после постройки дорог оказалось, что такая планировка не всегда удобна, поскольку для постройки больших заводов или других сооружений и организации парков недостаточно одного квартала. Мэрия города М решила отдать каждому большому проекту по прямоугольному блоку из нескольких соседних кварталов. К сожалению, после реализации проекта все дороги внутри такого блока будут закрыты для проезда, но по границе блоков проезд все еще будет возможен. Касание двух блоков не закрывает проезд между ними.
Когда Мэру города М принесли на согласование план распределения территорий для больших проектов, ему стало интересно, насколько сложным будет маршрут от мэрии до его будущего дома. Мэрия находится в центре нового района, на пересечении нулевой улицы, направленной с юга на север, и нулевой улицы, направленной с востока на запад. С итоговым расположением дома Мэр еще не определился и на выбор у него есть k вариантов. Каждый из вариантов находится на пересечении xi-ой улицы, направленной с юга на север (положительный x означает, что улица находится восточнее мэрии, отрицательный – западнее) и yi-ой улицы, направленной с востока на запад (положительный y означает, что улица находится севернее мэрии, отрицательный южнее).
Мэр считает, что маршрут до дома является сложным, если ему на этом маршруте придется совершить более двух поворотов направо или налево. Машина Мэра не может совершить более одного поворота на перекрестке, например, чтобы развернуться. Длина маршрута не имеет значения, и к дому можно подъезжать с любой стороны. Машина Мэра всегда стоит у мэрии в северном направлении, может повернуть сразу направо или налево, но не может развернуться.
Требуется написать программу, которая по информации о закрытых для проезда блоках кварталов и возможным расположениям дома Мэра, для каждого возможного расположения дома Мэра найдет несложный маршрут от мэрии до дома, определит кратчайший из них, или сообщит, что такого маршрута не существует. Количество поворотов минимизировать не требуется.
Входные данные
Первая строка входного файла INPUT.TXT содержит два целых числа n и k (0 ≤ n ≤ 100 000, 1 ≤ k ≤ 10) – количество блоков кварталов, которые по плану будут отданы большим проектам и количество вариантов расположения дома Мэра, соответственно.
Последующие n строк содержат по описанию блоков кварталов четыре целых числа u1, v1, u2, v2 (–109 ≤ u1 < u2 ≤ 109, –109 ≤ v1 < v2 ≤ 109) — номера улиц, на пересечении которых расположены противоположные углы блока кварталов, отданных под застройку и закрытых для проезда.
Последующие последние k строк содержат по два целых числа xi и yi (|xi| ≤ 109, |yi| ≤ 109, xi ≠ 0 или yi ≠ 0) — возможные расположения дома Мэра.
Мэрия и никакое из возможных расположений дома Мэра не находятся внутри блоков кварталов, отданных под застройку, но блоки кварталов, отданные под застройку, могут пересекаться.
Выходные данные
В выходной файл OUTPUT.TXT для каждого из возможных расположений дома Мэра в порядке появления во входном файле необходимо вывести сообщение, существуют ли несложный маршрут от мэрии до дома Мэра и, если существует, то где надо сделать повороты.
Если не существует несложный маршрут, то сообщение должно содержать слово NO на одной строке. Иначе, в первой строке должно содержаться слово YES, во второй строке – одно число t (0 ≤ t ≤ 2) количество поворотов, и в последующих t строках – описания поворотов в порядке их совершения: в каждой строке по три числа x, y и d номера улиц, на которых расположен перекресток, где необходимо повернуть, и направление поворота, при этом d = –1 означает поворот налево и d = 1 – поворот направо.
Координаты перекрестков, где необходимо совершить повороты, не должны превышать 109. Если кратчайших несложных путей несколько, необходимо вывести любой из них.
Примеры
| № | INPUT.TXT | OUTPUT.TXT |
|---|
| 1 | 1 2
-2 1 9 2
2 0
3 3 | YES
1
0 0 1
NO |
| 2 | 2 1
0 2 2 4
1 0 4 2
3 3 | YES
2
0 2 1
3 2 -1 |
| 3 | 0 2
0 -1
0 1 | NO
YES
0 |
Пояснения
Следующий рисунок демонстрирует решение для второго примера:
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
| |
