Fişierul intrare/ieşire:dreptunghi2.in, dreptunghi2.outSursăONIS 2014, Runda 3
AutorPaul DiacAdăugată defmins123FMI No Stress fmins123
Timp execuţie pe test0.5 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Dreptunghi2

Fie N puncte in plan de coordonate cunoscute (xi, yi) cu valori intregi. Un dreptunghi incadreaza aceste puncte daca toate punctele se afla in interiorul drepunghiului sau pe laturile lui. Determinati aria minima a unui dreptungi care incadreaza toate cele N puncte si are laturile paralele cu prima sau a doua bisectoare a axelor de coordonate.

Prima bisectoare a axelor de coordonate este dreapta care are ecuatia x - y = 0 iar a doua bisectoare dreapta cu ecuatia x + y = 0.

Date de intrare

Fişierul de intrare dreptunghi2.in contine pe prima linie numarul de teste T. In continuare, urmeaza descrierea fiecarui test astfel:
Pe prima linie numarul natural N iar pe urmatoarele N linii cate doua numere intregi xi yi separate prin spatiu.

Date de ieşire

În fişierul de ieşire dreptunghi2.out afisati un singur numar, aria minima a unui dreptunghi ce respecta restrictiile rotunjita la primele 3 zecimale.
În cazul in care toate punctele se afla pe un segment consideram un dreptunghi degenerat de arie 0 (se afiseaza 0.000).

Restricţii

  • 1 ≤ N ≤ 105
  • -104 ≤ xi, yi ≤ 104
  • Fisierul de intrare va contine maxim 10 teste

Exemplu

dreptunghi2.indreptunghi2.out
1
6
1 1
-2 1
1 4
-1 3
3 0
-2 5
30.000

Explicaţie

Coordonatele varfurilor drepunghiului sunt :
(1, -2), (4, 1), (-1, 6), (-4, 3)

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content