Задача: Прямоугольник на плоскости [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 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 |
#include #include //sort pairs of coordinates by value void sbv(double &x1, double &x2, double &y1, double &y2) { if( x1 > x2 ) std::swap( x1 , x2 ); if( y1 > y2 ) std::swap( y1 , y2 ); } //find whether the rectangles intersect bool intersect( double b1, double e1, double b2, double e2 ) { //"b" for "beginning", "e" for "end" (imagine the line segments on the coordinate axis) if( b2 >= e1 || e2 <= b1 ) return false; return true; } int main() { double a, b, c, d; //meaningful coodinates of rectangle sides int n; scanf( "%d", &n ); scanf( "%lg %lg %lg %lg", &a, &b, &c, &d ); double x1 = a, x2 = b, y1 = c, y2 = d; //"x" and "y" pairs are for rectangle of common area for( int i=1; i<n; i++ ) { scanf( "%lg %lg %lg %lg", &a, &b, &c, &d ); //refresh the coords. if( intersect( x1, x2, a, b ) && intersect( y1, y2, c, d ) ) //if they intersect { sbv( a, x1, x2, b ); //sort again to find the inner points sbv( c, y1, y2, d ); //(image is attached) printf("Common area of %d rectangles S = %lg\n", i+1, (y2-y1)*(x2-x1) ); } else { printf("System of rectangles has no common area.\n"); break; } } return 0; } |
Алгоритм решения:
1. Для удобства, запрограммировать задачу можно, сведя её к одномерному случаю: рассматривать проекции сторон прямоугольников на координатные оси. (см. рис. 1)
2. Проверка на пересечение: данные прямоугольники пересекаются и имеют общую площадь, если их проекции имеют общий интервал значений, больший одной точки.
3. Так как запоминать габариты прямоугольников нельзя по условию, работать будем с габаритами «общего» прямоугольника, которые сохраняются соотв. в переменные [latex]x1 \le x2, y1 \le y2[/latex]. Если новый прямоугольник пересекается с «общим», то определить обновленные габариты общего прямоугольника и рассчитать площадь(см. рис. 2). Если не пересекается, то выполнение программы прерывается, т.к. нужно вывести площадь прямоугольника, общего для всех [latex]n[/latex] прямоугольников.
Значения переменных в условии задачи не ограничены, так что для хранения габаритов был использован тип double, для всех порядковых переменных — тип int.
Протестировать решение можно по ссылке.
20-ая строчка: » «. Исправь
Назовите свою запись именем задачи (из таблицы). Сейчас она безымянная.
Исправлено.
Засчитано.
Но в условии пропущено важное слово.) Вести нужно не n, а «n прямоугольников».
Исправлено.