Se consideră două semidrepte orizontale paralele notate $a$ şi $b$. Fiecare dintre ele are capătul din stânga situat pe axa $Oy$. Distanţa dintre ele este de două unităţi.
Pe semidreapta $a$ se află $n_1$ puncte iar pe semidreapta $b$ se află $n_2$ puncte. Pentru fiecare dintre aceste puncte se cunoaşte distanţa faţă de axa $Oy$.
Cerinţă
Să se determine :
- Câte trapeze dreptunghice, cu una dintre baze pe semidreapta $a$, cu cealaltă bază pe semidreapta $b$ şi cu vârfurile în cele două mulțimi de puncte date se pot forma?
- Care este cea mai mare arie a unuia dintre aceste trapeze?
Date de intrare
Fişierul trapeze.in are următorul conţinut:
- Pe prima linie se află un număr natural $n_1$, cu semnificația din enunţ.
- Pe a doua linie se află $n_1$ valori separate prin câte un spațiu. Fiecare dintre acestea reprezintă distanţa de la unul dintre cele $n_1$ puncte situate pe semidreapta $a$ la axa $Oy$.
- Pe a treia linie se află un număr natural $n_2$, cu semnificația din enunţ.
- Pe a doua linie se află $n_2$ valori separate prin câte un spațiu. Fiecare dintre acestea reprezintă distanţa de la unul dintre cele $n_2$ puncte situate pe semidreapta $b$ la axa $Oy$.
Date de ieșire
Fișierul trapeze.out va conţine două linii:
- Pe prima linie se va afla un număr natural reprezentând răspunsul la cerinţa $1$.
- Pe a doua linie se va afla un număr natural reprezentând răspunsul la cerinţa $2$.
Restricții și precizări:
- un trapez este un patrulater cu două laturi paralele denumite baze şi celelalte două laturi neparalele. Dreptunghiurile, pătratele, paralelogramele şi romburile NU sunt trapeze!
- un trapez dreptunghic este un trapez în care bazele sunt perpendiculare pe una dintre laturile neparalele.
- aria unui trapez dreptunghic este egală cu produsul dintre suma bazelor şi lungimea laturii perpendiculare împărțit la $2$;
- $ 2 \leq n_1, n_2 \leq 100 000$;
- valorile de pe a doua linie şi de pe a patra linie nu depășesc $1$ miliard;
- valorile de pe a doua linie și de pe a patra linie sunt date în ordine crescătoare;
- se garantează că punctele date formează cel puțin un trapez dreptunghic;
- 50% din punctajul total se acordă pentru rezolvarea corectă a unor teste în care $n_1$ şi $n_2 \leq 200$
Exemplu
trapeze.in
4
1 3 6 9
5
2 3 4 6 10
trapeze.out
12
13
Explicații
Pe semidreapta $a$ se găsesc $4$ puncte aflate la distanțele $1$, $3$, $6$ și $9$ față de $Oy$.
Pe semidreapta $b$ se găsesc $5$ puncte aflate la distanțele $2$, $3$, $4$, $6$ și $10$ față de $Oy$.
Numărul de trapeze dreptunghice cu o bază pe semidreapta $a$ și cealaltă bază pe semidreapta $b$ este $12$ iar cea mai mare arie a unui astfel de trapez este $13$.