# PBinfo #1244 – Trapeze – Rezolvare C++

Sursa: Codul lui Andrei
Limbaj: C++
Autor rezolvare: deivid

## Enunț

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 :


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 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.

## Cod sursă C++

```cpp
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
vector <int> vp,psta,pstb;
ifstream f("trapeze.in");
ofstream g("trapeze.out");
int n1,n2,a[100001],b[100001];
int i,j;
long long ariahdr, ariahst, ariamax, nrperechi, rez;
int main()
{
    cout << "Hello world!" << endl;
    f >> n1;
    for (i=0;i<n1;i++)
        f >> a[i];
    f >> n2;
    for (i=0;i<n2;i++)
        f >> b[i];
    i=j=0;
    while (i<n1 && j<n2)
        if (a[i]==b[j])
        {
            vp.push_back(a[i]);
            psta.push_back(i);
            pstb.push_back(j);
            i++;j++;
        }
        else
            if (a[i]<b[j])
                i++;
            else
                j++;
    nrperechi = vp.size();
    //cout << nrperechi << endl;
    //for (i=0;i<vp.size();i++)
    //    cout << vp[i]<< " " <<psta[i]<< " " <<pstb[i]<<endl;
    long long nrsta, nrstb, nrdra, nrdrb, baza1, baza2;
    for (i=0;i<vp.size();i++)
        {
            nrsta = psta[i];//cate puncte are in stanga pe a
            nrstb = pstb[i];//si pe b
            nrdra = n1 - 1 - psta[i];//cate puncte are in dreapta pe a
            nrdrb = n2 - 1 - pstb[i];//si pe b
            long long nrtrapst = nrsta*nrstb - i;
            long long nrtrapdr = nrdra*nrdrb - (nrperechi - i - 1);
            //cout << i <<  << nrtrapst <<  << nrtrapdr << endl;
            rez += nrtrapdr + nrtrapst;
        }
    cout << rez << endl;
    g << rez << endl;
    int xa1, xa2, xb1, xb2;
    // calculez aria trapezului cu inaltimea cea mai din stanga
    xa1 = xb1 = vp[0];
    nrdra = n1 - 1 - psta[0];//cate puncte are in dreapta a
    nrdrb = n2 - 1 - pstb[0];//cate puncte are in dreapta b
    //cout << nrdra <<  << nrdrb<<endl;
    if (nrdra==0 || nrdrb == 0)//evident
        ariahst = 0;
    else
        if (a[n1-1]!= b[n2-1])//punctele din capete nu sunt aliniate=>trapez cu ele
        {
            xa2 = a[n1-1];
            xb2 = b[n2-1];
            baza1 = xa2 - xa1;
            baza2 = xb2 - xb1;
            ariahst = baza1+baza2;
        }
        else    //punctele din capete sunt aliniate
        {
          if (nrdra==1 && nrdrb==1)//o singura pereche in dreapta aliniata=> niciun trapez spre dreapta
            ariahst=0;
          if (nrdra==1 && nrdrb>1)//1 punct pe a , mai multe pe b
            {
                xa2 = a[n1-1];//iau utimul si singurul de pe a
                xb2 = b[n2-2];//cu penultimul de pe b cu care sigur nu e aliniat
                baza1 = xa2 - xa1;baza2 = xb2 - xb1;
                ariahst = baza1+baza2;
            }
          if (nrdra>1 && nrdrb==1)//mai multe pe a, 1 pe b - analog
            {
                xa2 = a[n1-2];
                xb2 = b[n2-1];
                baza1 = xa2 - xa1;baza2 = xb2 - xb1;
                ariahst = baza1+baza2;
            }
          if (nrdra>1 && nrdrb>1)
            {
                xa2 = a[n1-1];//ultimul pe a, penultimul pe b
                xb2 = b[n2-2];
                baza1 = xa2 - xa1; baza2 = xb2 - xb1;
                ariahst = baza1+baza2;
                xa2 = a[n1-2];//penultimul pe a, ultimul pe b
                xb2 = b[n2-1];
                baza1 = xa2 - xa1; baza2 = xb2 - xb1;
                if (baza1+baza2 > ariahst)
                    ariahst = baza1+baza2;
            }
        }
    cout << ariahst<<endl;
    xa2 = xb2 = vp[nrperechi-1];
    nrsta = psta.size()-1; //cate puncte are in stanga pe a
    nrstb = pstb.size()-1; //cate puncte are in stanga pe b
   // cout << nrsta <<  << nrstb << endl;
    if (nrsta==0 || nrstb == 0)//evident
        ariahdr = 0;
    else
        if (a[0] != b[0])//punctele din capete nu sunt aliniate=>trapez cu ele
        {
            xa1 = a[0];
            xb1 = b[0];
            baza1 = xa2 - xa1;
            baza2 = xb2 - xb1;
            ariahdr = baza1+baza2;
        }
        else    //punctele din capete sunt aliniate
        {
          if (nrsta==1 && nrstb==1)//o singura pereche in dreapta aliniata=> niciun trapez spre dreapta
            ariahdr=0;
          if (nrsta==1 && nrstb>1)//1 punct pe a , mai multe pe b
            {
                xa1 = a[0];//iau primul si singurul de pe a
                xb1 = b[1];//cu al doilea de pe b cu care sigur nu e aliniat
                baza1 = xa2 - xa1;baza2 = xb2 - xb1;
                ariahdr = baza1+baza2;
            }
          if (nrsta>1 && nrstb==1)//mai multe pe a, 1 pe b - analog
            {
                xa1 = a[1];
                xb1 = b[0];
                baza1 = xa2 - xa1;baza2 = xb2 - xb1;
                ariahdr = baza1+baza2;
            }
          if (nrdra>1 && nrdrb>1)
            {
                xa1 = a[0];//primul pe a, al doilea pe b
                xb1 = b[1];
                baza1 = xa2 - xa1; baza2 = xb2 - xb1;
                ariahdr = baza1+baza2;
                xa1 = a[1];//penultimul pe a, ultimul pe b
                xb1 = b[0];
                baza1 = xa2 - xa1; baza2 = xb2 - xb1;
                if (baza1+baza2 > ariahdr)
                    ariahdr = baza1+baza2;
            }
        }
    cout << ariahdr<<endl;
    ariamax = ariahdr > ariahst? ariahdr: ariahst;
    cout << ariamax<<endl;
    g << ariamax<<endl;
    return 0;
}
```

## Resurse

- [Pagina originală](https://codulluiandrei.ro/rezolvari/pbinfo/1244)
- [Sursa C++](https://codulluiandrei.ro/rezolvari/pbinfo/1244/cod.cpp)
- [Sursa pe GitHub](https://raw.githubusercontent.com/codulluiandrei/pbinfo/main/pbinfo-1244/main.cpp)
- [Cursuri de informatică pentru BAC](https://codulluiandrei.ro/academia/info-curs/pachet-cpp/)