Sum of polynomials P70952

Here we consider sums of polynomials with integer coefficients. For instance, the sum of $12+2x-15x^2+4x^3$ and $-1-3x+15x^2-2x^4$ is $11-x+4x^3-2x^4$.

We represent the polynomials with vectors of pairs, with the coefficient and the exponent of a monomial, whenever the coefficient is not zero. The vector is sorted in increasing order by the exponents.

For instance, the polynomial $12+2x-15x^2+4x^3$ corresponds to the vector

and the polynomial $666x-x^{79}+12x^{191}$ corresponds to the vector

The following declarations allow us to define polynomials as described:

    struct Pair {
        int coef;                           // coefficient
        int expo;                           // exponent
    };

    typedef vector<Pair> Polynomial;        // sorted by exponent

Using these definitions, implement the function

    Polynomial sum(const Polynomial& p, const Polynomial& q); 

that returns the sum of two given polynomials @p@ and @q@.

Observation

The main program is already implemented: do not modify it. First, it reads a number $t$. Afterwards, it reads $t$ pairs of polynomials, adds them up and prints the result.

#include <iostream>
#include <vector>
using namespace std;


struct Pair {
    int coef;
    int expo;
};


typedef vector<Pair> Polynomial;


Polynomial sum(const Polynomial& p, const Polynomial& q) {
}


void read(Polynomial& p) {
    int n;
    cin >> n;
    p = Polynomial(n);
    char c;
    for (int i = 0; i < n; ++i) cin >> p[i].coef >> c >> p[i].expo;
}


void print(const Polynomial& p) {
    int n = p.size();
    cout << n;
    for (int i = 0; i < n; ++i) cout << " " << p[i].coef << ":" << p[i].expo;
    cout << endl;
}


int main() {
    int t;
    cin >> t;
    for (int i = 0; i < t; ++i) {
        Polynomial p, q;
        read(p);
        read(q);
        Polynomial r = sum(p, q);
        print(r);
    }
}