Задача ЛАБИРИНТ
В результате рейда налоговой полиции города Обломова в фирму Real в одном из небоскребов был обнаружен секретный уровень, на который вела только одна лестница, а в некоторых местах были аварийные выходы (в виде люков в полу). Согласно агентурным данным, уровень представляет собой прямоугольник из N*M комнат одинакового размера (M комнат вдоль западной стены, N – вдоль северной), причем между некоторыми парами соседних комнат есть двери. Положение осложняется тем, что точные координаты как входа, так и выходов неизвестны.
На разведку были отправлены обезьянки из местного зоопарка. Каждая из них поднималась по лестнице и ходила по уровню, пока не натыкалась на какой-нибудь выход. После этого она спускалась по нему и сообщала свой маршрут начальству. При этом первая обезьянка в начальной точке смотрела на север, а остальные – неизвестно куда. Маршрут каждой обезьянки представлен в виде последовательности символов, представляющих движения и повороты:
F шаг вперед
R поворот направо
L поворот налево
B разворот
W впереди стена, движения не было
E выход, конец маршрута (может идти только непосредственно после F)
Задача состоит в том, чтобы построить план обследованной части уровня, содержащий всю собранную информацию: стенки, проходы, выходы.
Входной файл: Input.txt
Выходной файл: Output.txt
Время тестирования: 20 секунд.
Входные данные:
В первой строке входного потока задаются числа M и N, разделённые пробелами. На следующей строке задаётся общее количество маршрутов. Далее идут маршруты представляющие собой последовательность символов F, R, L, B, W, E, возможное, разделённых пробельными символами. Каждый маршрут закачнивается символом E,, после которого начинается следующий маршрут.
Ограничения:
Входные данные удовлетворяют следующим ограничениями: 1< M<50, 1<N<50,, общее количество маршрутов -- не более 100, общее количество символов в записи маршрутов -- не более 255.
Результат, прграмма должна напечатать карту уровня размера (2*M+1)*(2*N+1), нарисованную символами:
(<<пробел>>) пустая комната или проход
+ угол комнаты
- северная/южная сторона
| задапдная/восточная стенка
* вход
# выход
? неизвестное состояние комнаты или стенки
Если существует несколько планов уровней, удовлетворяющих условиям задачи, достаточно напечатать любой, если план построить не удаётся, программу должна напечатать строку NO.
Задача:
Задана 4. «Прямоугольники»
Задача предлагалась в 1998 году на олимпиаде первокурсников факультета ПММ ВГУ
Условие задачи
На плоскости задано N прямоугольников с координатами вершин (X1i, Y1i), (Х2і, Y2i), (ХЗі, УЗі), (Х4і, У4i), і = 1,2,3,..., N. Известно, что все стороны прямоугольников параллельны осям координат. Все прямоугольники являются замкнутыми множествами, то есть содержат свою границу. Будем считать, что прямоугольники пересекаются, если они имеют хотя бы одну общую точку ( в том числе и на границе).
Необходимо определить количество фигур, образованных в результате наложения прямоугольников.
Входные данные
В первой строке (1 < =N< =100) — число прямоугольников.
В каждой последующей — их координаты, заданные целыми числами:
-1000<=X1i, Y1i, X2i, Y2i, X3i, Y3i, X4i, Y4i<=1000 i=1,2,3,...N
Выходные данные
Число фигур.