| Codeforces Round 168 (Div. 1) |
|---|
| Закончено |
Представьте таблицу размера n × m, где некоторые ячейки заблокированы. У ячейки в верхнем левом углу координаты — (1, 1), а у ячейки в правом нижнем углу — (n, m). Всего в таблице существуют k заблокированных ячеек, остальные ячейки — пустые. Вы пускаете луч лазера из центра пустой ячейки (xs, ys) в одном из диагональных направлений (то есть северо-восток, северо-запад, юго-запад или юго-восток). Если луч попадает в заблокированную ячейку или на границу таблицы, то он отражается. Поведение отражения луча в разных ситуациях показано на рисунке ниже.
Заметим, что через некоторое время луч попадает в бесконечный цикл. Посчитайте количество пустых ячеек, через которые луч проходит хотя бы однажды. Считается, что луч проходит через ячейку, если он проходит через ее центр.
Первая строка входных данных содержит три целых числа n, m и k (1 ≤ n, m ≤ 105, 0 ≤ k ≤ 105). Каждая из следующих k строк содержит два целых числа xi и yi (1 ≤ xi ≤ n, 1 ≤ yi ≤ m), числа обозначают положение i-ой заблокированной ячейки.
Последняя строка содержит два целых числа xs, ys (1 ≤ xs ≤ n, 1 ≤ ys ≤ m) и направление луча, равное «NE», «NW», «SE» или «SW». Эти строки соответствуют направлениям ( - 1, 1), ( - 1, - 1), (1, 1), (1, - 1).
Гарантируется, что никакие две блокируемые ячейки не имеют одинаковых координат.
В единственной строке выходных данных выведите количество пустых ячеек, через которые луч проходит хотя бы раз.
Пожалуйста, не используйте спецификатор %lld для чтения или записи 64-х битовых чисел на С++. Рекомендуется использовать потоки cin, cout или спецификатор %I64d.
3 3 0
1 2 SW
6
7 5 3
3 3
4 3
5 3
2 1 SE
14
