Школа программиста

Забыли пароль?
[задачи] [курсы] [олимпиады] [регистрация]
Логин:   Пароль:    
Скрыть меню
О школе
Правила
Олимпиады
Фотоальбом
Гостевая
Форум
Архив олимпиад
Архив задач
Состояние системы
Рейтинг
Курсы
Новичкам
Работа в системе
Алгоритмы
Курсы ККДП
Дистрибутивы
Ссылки

HotLog


 

Дом Мэра

(Время: 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.TXTOUTPUT.TXT
11 2
-2 1 9 2
2 0
3 3
YES
1
0 0 1
NO
22 1
0 2 2 4
1 0 4 2
3 3
YES
2
0 2 1
3 2 -1
30 2
0 -1
0 1
NO
YES
0

Пояснения

Следующий рисунок демонстрирует решение для второго примера:


Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!

 Язык программирования C++
 Решение олимпиадных задач
 Региональные олимпиады
 Книги Фёдора Меньшикова
 Тренировочные олимпиады
 Школьный этап
 Муниципальный этап
 Региональный этап
 Полуфинал ВКОШП
 Личное первенство СФУ
 2006 / 2007
 2007 / 2008
 2008 / 2009
 2009 / 2010
 2010 / 2011
 2011 / 2012
 2012 / 2013
 2013 / 2014
 2014 / 2015
 2015 / 2016
 2016 / 2017
 2017 / 2018
 2018 / 2019
 2019 / 2020
 A. POBEDA-2014
 B. Список школ
 C. Межрегиональная олимпиада
 D. Дом Мэра
 E. Светофоры
 F. Кондиционеры
 G. Конфеты
 H. Волонтеры

Красноярский краевой Дворец пионеров, (c)2006 - 2020, E-mail: admin@acmp.ru