| Fişierul intrare/ieşire: | drepte3.in, drepte3.out | Sursă | Summer Challenge 2009, Runda 1 |
| Autor | Cosmin Silvestru Negruseri | Adăugată de |  Marius Stroe •Marius |
| Timp execuţie pe test | 0.125 sec | Limită de memorie | 20480 kbytes |
| Scorul tău | N/A | Dificultate | N/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.in | drepte3.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.
