Задача 19.
Задано на плоскости множество из N прямоугольников, стороны которых параллельны осям координат, при этом каждый прямоугольник задается координатами левой нижней и правой верхней его вершин.
Составить алгоритм определения наибольшего натурального числа К, для которого существует точка плоскости, принадлежащая одновременно К прямоугольникам.
Примечание: эффективным считается алгоритм, число действий которого пропорционально Н2.
|
Решение задачи 19.
На первом этапе на основании координат вершин прямоугольников формируем 4 массива: массив Х-овых координат вершин прямоугольника и связанный с ним массив номеров прямоугольников,вершина которого соответствует данной Х-овой координате;аналогично формируются массивы для У-овых координат. При этом координате вершины ставится в соответствие номер со знаком "+", если вершина левая нижняя, и знак "-", если правая верхняя.
На втором этапе массивы координат сортируются в порядке неубывания (при этом соответствие между координатами и вершинами сохраняется), причем для одинаковых координат вначале должны располагаться номера левых нижних вершин (т.е. со знаком "+"), а затем номера правых верхних. Это легко делается, если рассматривать номера как вторые значения для сортировки.
На следующих этапах проводится просмотр необходимых точек (будут рассмотрены все точки, лежащие на пересечении горизонтальных и вертикальных линий, проходящих через вершины прямоугольников) следующим образом. Формируется массив активных прямоугольников по У-овым координатам. Для этого, начиная с минимальной У-овой координаты, доходим до ближайшей координаты, у которой номер вершины имеет знак "-" или ее координата отлична от предыдущей координаты. При этом номера всех пройденных вершин активизируем. Для этого в массиве АКТИВНАЯ на соответствующее место ставим 1 или 0 (вначале все элементы массива равны 0). 1 ставится при прохождении вершины со знаком "+", 0- со знаком "-".
После поиска нужной У-овой координаты просматриваем все Х-овые координаты по такому же принципу, как при нахождении максимального пересечения отрезков (т.е. если встречаем вершину со знаком "+", то текущее количество пересечений увеличиваем на 1, а если встречаем вершину со знаком "-", то уменьшаем на 1). При этом
учитывается, активна ли встреченная вершина. Таким образом, изменение текущего количества пересечений выполняется только для активных вершин. После вычисления максимального значения пересечения для текущей У-овой координаты переходим к очередной У-овой координате. Описанные действия выполняются, пока все У-овые координаты не будут просмотрены.
|
