Квадратне пасовище#10556

Квадратне пасовище (Розбір)

Нехай координати прямокутників задані наступним чином:

$(x_{1}, y_{1}) - (x_{2}, y_{2})$ (x_1, y_1) - (x_2, y_2): перший прямокутник, $x_{1} < x_{2}, y_{1} < y_{2}$ x_1 < x_2, y_1 < y_2,
$(x_{3}, y_{3}) - (x_{4}, y_{4})$ (x_3, y_3) - (x_4, y_4): другий прямокутник, $x_{3} < x_{4}, y_{3} < y_{4}$ x_3 < x_4, y_3 < y_4

Розглянемо мінімальний за розмірами прямокутник, який повністю покриває обидва вихідні прямокутники. Позначимо його протилежні кути як $(min x, min y)$ (minx, miny) і $(ma xx, ma x y)$ (maxx, maxy). Тоді:

$min x = min (x_{1}, x_{3}), min y = min (y_{1}, y_{3})$ minx = min(x_1, x_3), miny = min(y_1, y_3),
$ma xx = ma x (x_{2}, x_{4}), ma x y = ma x (y_{2}, y_{4})$ maxx = max(x_2, x_4), maxy = max(y_2, y_4)

Розміри покриваючого прямокутника рівні:

$l e n g t h = ma xx - min x$ length = maxx - minx,
$w i d t h = ma x y - min y$ width = maxy - miny

Щоб обидва прямокутники можна було повністю покрити квадратом, сторона квадрата повинна бути не меншою як $l e n g t h$ length, так і $w i d t h$ . Тому довжина сторони мінімального квадратного пасовища рівна максимуму з цих двох величин:

s i d e = ma x (l e n g t h, w i d t h)

side = max(length, width)

Приклад

Розглянемо два вихідні прямокутники:

перший прямокутник має нижній лівий кут $(6, 6)$ і верхній правий кут $(8, 8)$ ,
другий прямокутник має нижній лівий кут $(1, 8)$ і верхній правий кут $(4, 9)$

Обчислимо межі результуючого прямокутника:

$min x = min (6, 1) = 1, min y = min (6, 8) = 6$ minx = min(6, 1) = 1, miny = min(6, 8) = 6,
$ma xx = ma x (8, 4) = 8, ma x y = ma x (8, 9) = 9$ maxx = max(8, 4) = 8, maxy = max(8, 9) = 9

Розміри покриваючого прямокутника рівні:

$l e n g t h = 8 - 1 = 7$ length = 8 - 1 = 7,
$w i d t h = 9 - 6 = 3$ width = 9 - 6 = 3

Довжина сторони покриваючого квадрата становитиме:

s i d e = ma x (7, 3) = 7

side = max(7, 3) = 7

Отже, площа мінімального покриваючого квадрата рівна $7^{2} = 49$ 7^2 = 49.

Реалізація алгоритму

Ініціалізуємо межі покриваючого прямокутника. Оскільки координати знаходяться в діапазоні від $0$ до $10$ , можна встановити початкові значення наступним чином:

minx = 10; maxx = 0; miny = 10; maxy = 0;

Читаємо координати двох вихідних прямокутників. Для кожного прямокутника оновлюємо межі покриваючого прямокутника.

for (i = 0; i < 2; i++)
{
  scanf("%d %d %d %d", &a1, &b1, &a2, &b2);
  if (a1 < minx) minx = a1;
  if (a2 > maxx) maxx = a2;
  if (b1 < miny) miny = b1;
  if (b2 > maxy) maxy = b2;
}

C++

Обчислюємо довжину і ширину покриваючого прямокутника.

l = maxx - minx;
w = maxy - miny;

Щоб покрити цей прямокутник квадратом, сторона квадрата повинна бути не меншою як його довжини, так і ширини. Тому вибираємо більшу з двох величин.

len = (l > w) ? l : w;

Обчислюємо площу квадрата і виводимо відповідь.

area = len * len;
printf("%d\n", area);