Ю 3.4

Задача: Прямоугольник на плоскости [latex]a \le x \le b, \quad c \le y \le d[/latex] задаётся четырьмя числами (его габаритами): [latex]a, b, c, d.[/latex] Последовательно вводятся габариты [latex]n[/latex] прямоугольников. В процессе ввода находить площадь их пересечения, не запоминая самих габаритов.

NI — «no intersection» — нет общего сегмента

[latex]a[/latex] [latex]b[/latex] [latex]c[/latex] [latex]d[/latex] [latex]S[/latex] Комментарий
1 -5 -3 1 4 NI Пройден: нет общего интервала
-2 0 1 4
2 0 4.5 1.2 4.6 NI Пройден: нет общего интервала
2 4 5 7.4
3 2 5 1 4 NI Пройден: общая сторона не считается пересечением, т.к. даёт нулевую площадь
5 6 1 4
4 2 4 2 4 4 Пройден
2 4 2 4
5 2 5 1 4 NI Пройден: не все данные прямоугольники имеют общий сегмент
0 3 2 3
6 7 3 5
6 0 7 0 3 1 Пройден
2 6 1 5
3 5 2 5
4 8 2 3
 

Алгоритм решения:
1. Для удобства, запрограммировать задачу можно, сведя её к одномерному случаю: рассматривать проекции сторон прямоугольников на координатные оси. (см. рис. 1)
2. Проверка на пересечение: данные прямоугольники пересекаются и имеют общую площадь, если их проекции имеют общий интервал значений, больший одной точки.
3. Так как запоминать габариты прямоугольников нельзя по условию, работать будем с габаритами «общего» прямоугольника, которые сохраняются соотв. в переменные [latex]x1 \le x2, y1 \le y2[/latex]. Если новый прямоугольник пересекается с «общим», то определить обновленные габариты общего прямоугольника и рассчитать площадь(см. рис. 2). Если не пересекается, то выполнение программы прерывается, т.к. нужно вывести площадь прямоугольника, общего для всех [latex]n[/latex] прямоугольников.

Значения переменных в условии задачи не ограничены, так что для хранения габаритов был использован тип double, для всех порядковых переменных — тип int.

Протестировать решение можно по ссылке.

Іванов Вячеслав Володимирович
Іванов Вячеслав Володимирович

Latest posts by Іванов Вячеслав Володимирович (see all)

5 thoughts on “Ю 3.4