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

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

HotLog


 

Кинозал

(Время: 2 сек. Память: 32 Мб Сложность: 35%)

Однажды Вася пришёл в известный кинотеатр «Прямая», чтобы посмотреть новый боевик. Когда он проходил к своему месту в зале, то ему пришлось потревожить некоторых людей, которые заняли свои места раньше него. Он был этим так расстроен, что решил в следующий раз заранее определить минимальное количество людей, которым он должен помешать.

Известно, что кинозал имеет форму прямоугольника шириной W (количество мест в ряду) и высотой H (количество рядов). Каждая клетка внутри прямоугольника задаётся координатами (a, b) так, что 1 ≤ a ≤ H и 1 ≤ b ≤ W. Клетка может быть либо местом, на котором можно сидеть зрителю, либо быть часть прохода. Всего существует два типа проходов: вертикальный и горизонтальный, оба проходят от края до края. По проходам можно перемещаться свободно, не мешая зрителям. Дополнительно, по периметру зала тоже можно перемещаться свободно.

Вам дано описание зала с указанием проходов и уже занятых мест. Определите минимальное количество человек, которое необходимо потревожить Васе, чтобы добраться до своего места. Помимо прохождения по проходам, Вася может двигаться вдоль любого ряда. Считается, что Вася тревожит зрителя, если он проходит через его место на пути к своему. Аналогичное движение в направлении, перпендикулярном рядам, невозможно. Однако, если номер ряда места Васи на единицу больше координаты горизонтального прохода, то Вася его может занять, не потревожив зрителей. В направлении уменьшения координаты ряда Васи относительно горизонтальных проходов Вася двигаться не может, так как ему мешают спинки кресел.

Рассмотрим пример зрительного зала:

Здесь 9 рядов (H = 9) и 21 место в ряду (W =21). В зале помимо Васи 10 зрителей (обозначены кругами) со следующими координатами: (2,3), (9,7), (5,8), (1,9), (5,13), (1,15), (8,15), (5,17), (5,18), и (5,21). Место Васи обозначено смайликом и находится в координате (5,15). Также здесь три вертикальных прохода в координатах 5, 11, 19 и два горизонтальных прохода в координатах 3 и 7. Васе оптимально двигаться через вертикальный проход 11, потревожив всего одного зрителя (5,13). Вертикальные проходы Вася использовать не может. Но, если бы его ряд был на единицу меньше, то он смог бы через горизонтальный проход 3 занять свое место, не мешая другим зрителям.

Входные данные

В первой строке входного файла INPUT.TXT заданы четыре целых числа W, H, C и P (1 ≤ W, H ≤ 109, 0 ≤ C, P ≤ 105), где W и H — размеры кинозала, C — количество уже занятых мест, P — количество проходов.

В следующих P строках описаны проходы. Горизонтальный проход описывается как «hor hi» (1 ≤ hi ≤ H), а вертикальный — «vert vi» (1 ≤ vi ≤ W).

Затем в C строках записаны координаты (ai, bi) занятых мест (1 ≤ ai ≤ H, 1 ≤ b i ≤ W).

Последняя строка содержит координаты места Васи в аналогичном формате. Гарантируется, что ни одно место не указано дважды, а так же то, что места не находятся в проходах.

Выходные данные

В выходной файл OUTPUT.TXT выведите целое число — минимальное количество людей, которое нужно потревожить Васе.

Примеры

INPUT.TXTOUTPUT.TXTПояснение
110 5 8 2
vert 3
vert 8
2 2
5 6
1 7
3 4
3 6
3 7
4 10
1 4
3 5
1
25 5 2 2
hor 3
vert 4
4 1
4 3
4 2
0

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

 Язык программирования C++
 Решение олимпиадных задач
 Региональные олимпиады
 Книги Фёдора Меньшикова
 Тренировочные олимпиады
 Школьный этап
 Муниципальный этап
 Региональный этап
 Полуфинал ВКОШП
 Личное первенство СФУ
 2011 / 2012
 2012 / 2013
 2013 / 2014
 2014 / 2015
 2015 / 2016
 2016 / 2017
 2017 / 2018
 2018 / 2019
 A. Архимед
 B. Верхняя граница
 C. Волшебные цветы
 D. Двоичное упражнение
 E. Stack Unwinding
 F. Пробежка
 G. Три монеты
 H. Кинозал
 I. Индикатор загрузки
 J. Заверните две!
 K. Сладкая вата

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