Задача 22.
Очертание города.
Необходимо написать программу - помощник архитектора в рисовании очертания города. Город задается расположением зданий. Город рассматривается как двумерный и все здания в нем - прямоугольники, имеющие одинаковое основание (город построен на равнине). Здания задаются тройкой чисел (L[i],H[i],R[i]) где L[i] и R[i] есть координаты левой и правой стен здания i, а H[i] - высота этого здания. На рисунке 1 здания описываются тройками
(1,11,5), (2,6,7), (3,13,9), (12,7,16), (14,3,25), (19,18,22), (23,13,29),(24,4,28)
а контур, показанный на рис. 2, задается последовательностью
(1,11,3,13,9,0,12,7,16,3,19,18,22,3,23,13,29,0)
(о способе формировании этой последовательности см. ниже).
Рис. 1
Рис. 2
Ввод.
Ввод представляет собой последовательность троек, задающих дома. Все координаты есть целые числа, меньшие 10000. Во входном файле минимум одно и максимум 50 зданий. Каждая тройка, обозначающая здание находится в отдельной строке во входном файле. Все целые числа в тройке разделены одним или несколькими пробелами. Тройки отсортированы по L[i], т.е. по левой х-координате здания, таким образом, здание с самой маленькой левой х-координатой является первым во входном файле.
Вывод.
Вывод будет состоять из вектора, описывающего очертание, как показано в примере выше. В векторе очертания (v[1],v[2],v[3], ... , v[n-2],v[n-1],v[n]), v[i], когда i-четное число, означает горизонтальную линию (высоту). Когда i-нечетное, v[i]-означает вертикальную линию (х-координату). Вектор очертания будет определять маршрут, пройденный, к примеру, жуком, начавшим с минимальной х-координаты и путешествующим по всем вертикальным и горизонтальным линиям, определяющим контур. Последний элемент в векторе линии контура будет 0.
|
