Rezolvare PBinfo #1244

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ă n1 puncte iar pe semidreapta b se află n2 puncte. Pentru fiecare dintre aceste puncte se cunoaște distanța fața de axa Oy.

Cerinţă

Să se determine :

1. 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?
2. 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 n1, cu semnificația din enunț.
• Pe a doua linie se află n1 valori separate prin câte un spațiu. Fiecare dintre acestea reprezintă distanța de la unul dintre cele n1 puncte situate pe semidreapta a la axa Oy.
• Pe a treia linie se află un număr natural n2, cu semnificația din enunț.
• Pe a doua linie se află n2 valori separate prin câte un spațiu. Fiecare dintre acestea reprezintă distanța de la unul dintre cele n2 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 ≤ n1, n2 ≤ 100.000;
• valorile de pe a doua linie și de pe a patra linie nu depășesc 1.000.000.000;
• 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;
• pentru rezolvarea corectă a primei cerințe se acordă 50% din punctajul unui test; pentru rezolvarea corectă a ambelor cerințe se acordă 100% din punctajul testului.
• 50% din punctajul total se acordă pentru rezolvarea corectă a unor teste în care n1 și n2 ≤ 200

Exemplu:

trapeze.in

4
1 3 6 9
5
2 3 4 6 10

trapeze.out

12
13

Explicație

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.