Kvadrat otlaq#10556

Kvadrat otlaq (Həll təhlili)

Tutaq ki, düzbucaqlıların koordinatları aşağıdakı kimi verilib:

$(x_{1}, y_{1}) - (x_{2}, y_{2})$ (x_1, y_1) - (x_2, y_2): birinci düzbucaqlı, $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): ikinci düzbucaqlı, $x_{3} < x_{4}, y_{3} < y_{4}$ x_3 < x_4, y_3 < y_4

Hər iki başlanğıc düzbucaqlını tam əhatə edən minimal ölçülü düzbucaqlını nəzərdən keçirək. Onun qarşı bucaqlarını $(min x, min y)$ (minx, miny) və $(ma xx, ma x y)$ (maxx, maxy) kimi işarə edək. Onda:

$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)

Əhatə edən düzbucaqlının ölçüləri bərabərdir:

$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

Hər iki düzbucaqlının kvadratla tam əhatə oluna bilməsi üçün kvadratın tərəfi həm $l e n g t h$ length-dən, həm də $w i d t h$ -dən kiçik olmamalıdır. Buna görə minimal kvadrat otlağın tərəfinin uzunluğu bu iki kəmiyyətin maksimumuna bərabərdir:

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

side = max(length, width)

Misal

İki başlanğıc düzbucaqlını nəzərdən keçirək:

birinci düzbucaqlının aşağı sol bucağı $(6, 6)$ , yuxarı sağ bucağı $(8, 8)$ -dir,
ikinci düzbucaqlının aşağı sol bucağı $(1, 8)$ , yuxarı sağ bucağı $(4, 9)$ -dır

Nəticə düzbucaqlısının sərhədlərini hesablayaq:

$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

Əhatə edən düzbucaqlının ölçüləri bərabərdir:

$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

Əhatə edən kvadratın tərəfinin uzunluğu olacaq:

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

side = max(7, 3) = 7

Deməli, minimal əhatə edən kvadratın sahəsi $7^{2} = 49$ 7^2 = 49-a bərabərdir.

Alqoritmin realizasiyası

Əhatə edən düzbucaqlının sərhədlərini ilkinləşdirək. Koordinatlar $0$ -dan $10$ -a qədər diapazonda olduğundan, ilkin qiymətləri aşağıdakı kimi təyin etmək olar:

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

İki başlanğıc düzbucaqlının koordinatlarını oxuyuruq. Hər düzbucaqlı üçün əhatə edən düzbucaqlının sərhədlərini yeniləyirik.

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++

Əhatə edən düzbucaqlının uzunluğunu və enini hesablayırıq.

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

Bu düzbucaqlını kvadratla əhatə etmək üçün kvadratın tərəfi onun həm uzunluğundan, həm də enindən kiçik olmamalıdır. Buna görə iki kəmiyyətdən böyüyünü seçirik.

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

Kvadratın sahəsini hesablayırıq və cavabı çap edirik.

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