Fişierul intrare/ieşire:drepte3.in, drepte3.outSursăSummer Challenge 2009, Runda 1
AutorCosmin Silvestru NegruseriAdăugată deMariusMarius Stroe Marius
Timp execuţie pe test0.25 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Drepte3

Se dau N drepte în plan. Considerăm S mulţimea formată din punctele de intersecţie între oricare două drepte.

Cerinţă

Se cere să se determine aria minimă a dreptunghiului, cu laturile paralele cu axele de coordonate, care conţine toate punctele din mulţimea S.

Date de intrare

Fişierul de intrare drepte3.in conţine pe prima linie N, numărul dreptelor. Pe fiecare din următoarele N linii se vor găsi câte 3 numere întregi a b c, reprezentând coeficienţii ecuaţiei dreptei: ax + by + c = 0.

Date de ieşire

În fişierul de ieşire drepte3.out se va tipări un singur număr real reprezentând aria dreptunghiului cerut.

Restricţii şi precizări

  • 2 ≤ N ≤ 100 000
  • -105 ≤ a, b, c ≤ 105
  • Nu vor exista două drepte paralele.
  • Rezultatul se va considera corect dacă are o eroare de maxim 10-5.

Exemplu

drepte3.indrepte3.out
3
1 -1 0
0 1 -2
1 0 -1
1

Explicaţie

Mulţimea S = {(1, 1), (1, 2), (2, 2)}. Aria minimă a unui dreptunghi cu laturile paralele cu axele de coordonate, care să acopere cele trei puncte din S, este 1.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content