Определение наибольшего числа K, для которого существует точка плоскости, принадлежащая одновременно K прямоугольникам

06.05.2013, 17:26. **Показов** 1118. **Ответов** 0

Студворк — интернет-сервис помощи студентам

На плоскости задано множество из N прямоугольников,стороны которых параллельны осям координат,при этом каждый прямоугольник задается координатами левой нижней и правой верхней его вершин.Составить алгоритм определения наибольшего натурального числа K,для которого существует точка плоскости,принадлежащая одновременно K прямоугольникам.

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

Новые блоги и статьи Все статьи Все блоги /
Философия технологии iceja 01.02.2026 На мой взгляд у человека в технических проектах остается роль генерального директора. Все остальное нейронки делают уже лучше человека. Они не могут нести предпринимательские риски, не могут. . .	SDL3 для Web (WebAssembly): Вывод текста со шрифтом TTF с помощью SDL3_ttf 8Observer8 01.02.2026 Содержание блога В этой пошаговой инструкции создадим с нуля веб-приложение, которое выводит текст в окне браузера. Запустим на Android на локальном сервере. Загрузим Release на бесплатный. . .	SDL3 для Web (WebAssembly): Сборка C/C++ проекта из консоли 8Observer8 30.01.2026 Содержание блога Если вы откроете примеры для начинающих на официальном репозитории SDL3 в папке: examples, то вы увидите, что все примеры используют следующие четыре обязательные функции, а. . .	SDL3 для Web (WebAssembly): Установка Emscripten SDK (emsdk) и CMake для сборки C и C++ приложений в Wasm 8Observer8 30.01.2026 Содержание блога Для того чтобы скачать Emscripten SDK (emsdk) необходимо сначало скачать и уставить Git: Install for Windows. Следуйте стандартной процедуре установки Git через установщик. . . .
SDL3 для Android: Подключение Box2D v3, физика и отрисовка коллайдеров 8Observer8 29.01.2026 Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами. Версия v3 была полностью переписана на Си, в. . .	Инструменты COM: Сохранение данный из VARIANT в файл и загрузка из файла в VARIANT bedvit 28.01.2026 Сохранение базовых типов COM и массивов (одномерных или двухмерных) любой вложенности (деревья) в файл, с возможностью выбора алгоритмов сжатия и шифрования. Часть библиотеки BedvitCOM Использованы. . .	SDL3 для Android: Загрузка PNG с альфа-каналом с помощью SDL_LoadPNG (без SDL3_image) 8Observer8 28.01.2026 Содержание блога SDL3 имеет собственные средства для загрузки и отображения PNG-файлов с альфа-каналом и базовой работы с ними. В этой инструкции используется функция SDL_LoadPNG(), которая. . .	SDL3 для Android: Загрузка PNG с альфа-каналом с помощью SDL3_image 8Observer8 27.01.2026 Содержание блога SDL3_image - это библиотека для загрузки и работы с изображениями. Эта пошаговая инструкция покажет, как загрузить и вывести на экран смартфона картинку с альфа-каналом, то есть с. . .

Марина380

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