Пересечение прямоугольников

@PleaseHelpMe_ · Регистрация: 29.09.2021

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

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

Формат входных данных

В первой строке входных данных указано число N (1 <= N <= 1500). В последующих N строках заданы по 4 числа x1, y1, x2, y2 - сначала координаты левого нижнего угла прямоугольника, потом правого верхнего (-10^9 <= x1 <= x2 <= 10^9, -10^9 <= y1 <= y2 <= 10^9). Обратите внимание, прямоугольники могут вырождаться в отрезки или даже в точки.

Формат выходных данных

Выведите описание искомого прямоугольника в том же формате, в котором заданы прямоугольники во входных данных. Если пересечение заданных прямоугольников пусто, то выведите -1.

@PleaseHelpMe_ · 30.09.2021, 19:06 **[ТС]**

Помогите, пожалуйста, не могу понять, как найти пересечения N прямоугольников. Знаю, как найти двух, а вот N никак.

@TheCalligrapher · 30.09.2021, 20:30

Сообщение от PleaseHelpMe_

не могу понять, как найти пересечения N прямоугольников. Знаю, как найти двух, а вот N никак.

Не понял. Что значит "знаю, как найти двух, а вот N никак"? Если "знаю, как найти двух", то точно так же хоть миллион пересечь можно.

@PleaseHelpMe_ · 30.09.2021, 21:37 **[ТС]**

Я имею в виду, что вот есть алгоритм, как найти координаты пересечения двух прямоугольников.

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
//g++  7.4.0
 
#include <iostream>
using namespace std;
int main()
{
    long x1,y1,x2,y2, x11,y11,x12,y12;
    long x3, y3, x4, y4;
    cin >> x1 >> y1 >> x2 >> y2;
    cin >> x11 >> y11 >> x12 >> y12;
    x3 = max(x1, x11);
    y3 = max(y1, y11);
    x4 = min(x2, x12);
    y4 = min(y2, y12);
    cout << x3 << " " << y3 << " " << x4 << " " << y4;
}

Я не понимаю, как записать алгоритм для определения координат пересечения N прямоугольников.

@TheCalligrapher · 30.09.2021, 23:11

Сообщение от PleaseHelpMe_

Я не понимаю, как записать алгоритм для определения координат пересечения N прямоугольников.

1. Перечсечь первые два. Получить результат, который тоже - прямоугольник.
2. Пересечь результат шага 1 с третьим. Получить результат, который тоже - прямоугольник.
3. Пересечь результат шага 2 с четвертым. Получить результат, который тоже - прямоугольник.
4. И т.д. до N
5. Вывести последний результат.

Если в какой-то момент результат станет пустым, то дальше можно не пересекать.

@PleaseHelpMe_ · 01.10.2021, 20:24 **[ТС]**

Примерно так?

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <iostream>
using namespace std;
int main()
{
    long n;
    cin >> n;
    long long x1Result = -1000000000, y1Result = -1000000000, x2Result = 1000000000, y2Result = 1000000000;
    long long x1, y1, x2, y2;
    for (long long i = 0; i < n; i++) 
    {
        cin >> x1 >> y1 >> x2 >> y2;
        if ((x1 <= x2) && (y1 <= y2))
        {
            x1Result = max(x1Result, x1);
            y1Result = max(y1Result, y1);
            x2Result = min(x2Result, x2);
            y2Result = min(y2Result, y2);
        }
    }
    cout << x1Result << " " << y1Result << " " << x2Result << " " << y2Result;
}

Новые блоги и статьи Все статьи Все блоги /
SDL3 для Web (WebAssembly): Обработчик клика мыши в браузере ПК и касания экрана в браузере на мобильном устройстве 8Observer8 02.02.2026 Содержание блога Для начала пошагово создадим рабочий пример для подготовки к экспериментам в браузере ПК и в браузере мобильного устройства. Потом напишем обработчик клика мыши и обработчик. . .	Философия технологии 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(), которая. . .

@PleaseHelpMe_ 0 / 0 / 0 Регистрация: 29.09.2021 Сообщений: 6

	Пересечение прямоугольников 29.09.2021, 18:57. Показов 7537. Ответов 5 Метки нет (Все метки) На плоскости задано N прямоугольников с вершинами в точках с целыми координатами и сторонами, параллельными осям координат. Необходимо найти прямоугольник, являющимся их пересечением. Формат входных данных В первой строке входных данных указано число N (1 <= N <= 1500). В последующих N строках заданы по 4 числа x1, y1, x2, y2 - сначала координаты левого нижнего угла прямоугольника, потом правого верхнего (-10^9 <= x1 <= x2 <= 10^9, -10^9 <= y1 <= y2 <= 10^9). Обратите внимание, прямоугольники могут вырождаться в отрезки или даже в точки. Формат выходных данных Выведите описание искомого прямоугольника в том же формате, в котором заданы прямоугольники во входных данных. Если пересечение заданных прямоугольников пусто, то выведите -1. 0

@PleaseHelpMe_ 0 / 0 / 0 Регистрация: 29.09.2021 Сообщений: 6
	30.09.2021, 19:06 [ТС]
	Помогите, пожалуйста, не могу понять, как найти пересечения N прямоугольников. Знаю, как найти двух, а вот N никак. 0