Изменения
→Структура данных
*''трапецоиды''
Будем смотреть на левую сторону трапецоида.
У каждого трапецоида есть точка leftp(<tex>\Delta</tex>). Либо это конец какого-то отрезка, либо это левый нижний угол оболочки.
При этом можно сразу сказать, что левый и нижний угол будет соответствовать только одному трапецоиду.
Далее заметим, что правый конец отрезка может быть leftp(<tex>\Delta</tex>) только для одного трапецоида.
Левый конец может быть leftp(<tex>\Delta</tex>) максимум для двух трапецоидов.
Из этого следует, что количество трапецоидов n + 2n + 1 = 3n + 1.
}}
Хранить трапецоиды можно в чем угодно. Вместе с самим трапецоидом, стоит хранить leftp, rightp, top и bottom так же следует хранить соседей трапецоида.
