Recinto quadrato#10556

Recinto quadrato (Editoriale)

Supponiamo che le coordinate dei rettangoli siano date come segue:

$(x_{1}, y_{1}) - (x_{2}, y_{2})$ (x_1, y_1) - (x_2, y_2): primo rettangolo, $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): secondo rettangolo, $x_{3} < x_{4}, y_{3} < y_{4}$ x_3 < x_4, y_3 < y_4

Consideriamo il rettangolo di dimensioni minime che copre completamente entrambi i rettangoli originali. Indichiamo i suoi angoli opposti come $(min x, min y)$ (minx, miny) e $(ma xx, ma x y)$ (maxx, maxy). Allora:

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

Le dimensioni del rettangolo di copertura sono uguali a:

$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

Perché entrambi i rettangoli possano essere completamente coperti da un quadrato, il lato del quadrato deve essere non inferiore sia a $l e n g t h$ length che a $w i d t h$ . Pertanto, la lunghezza del lato del pascolo quadrato minimo è uguale al massimo di queste due quantità:

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

side = max(length, width)

Esempio

Consideriamo due rettangoli originali:

il primo rettangolo ha l'angolo inferiore sinistro $(6, 6)$ e l'angolo superiore destro $(8, 8)$ ,
il secondo rettangolo ha l'angolo inferiore sinistro $(1, 8)$ e l'angolo superiore destro $(4, 9)$

Calcoliamo i confini del rettangolo risultante:

$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

Le dimensioni del rettangolo di copertura sono uguali a:

$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

La lunghezza del lato del quadrato di copertura sarà:

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

side = max(7, 3) = 7

Di conseguenza, l'area del quadrato di copertura minimo è uguale a $7^{2} = 49$ 7^2 = 49.

Implementazione dell'algoritmo

Inizializziamo i confini del rettangolo di copertura. Poiché le coordinate si trovano nell'intervallo da $0$ a $10$ , possiamo impostare i valori iniziali come segue:

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

Leggiamo le coordinate dei due rettangoli originali. Per ciascun rettangolo, aggiorniamo i confini del rettangolo di copertura.

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

Calcoliamo la lunghezza e la larghezza del rettangolo di copertura.

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

Per coprire questo rettangolo con un quadrato, il lato del quadrato deve essere non inferiore sia alla sua lunghezza che alla sua larghezza. Pertanto, scegliamo la maggiore delle due quantità.

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

Calcoliamo l'area del quadrato e stampiamo la risposta.

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