#include <stdio.h>
#include <stdlib.h>
#include <math.h>

#define ZERO  1e-10

struct Polynomial {
    int deg;
    double* coeff;
};

struct Polynomial* makePolynomial(int deg) {
    struct Polynomial* p = malloc(sizeof(*p));
    p->deg = deg;
    p->coeff = malloc((deg + 1) * sizeof(*p->coeff));
    return p;
}

void findDeg(struct Polynomial* p) {
    for (int i = p->deg; i >= 0; i--)
        if (fabs(p->coeff[i]) > ZERO) {
            p->deg = i;
            return;
        }
    p->deg = 0;
}


struct Polynomial* addPolynomials(struct Polynomial* a, struct Polynomial* b) {
    int newDeg = a->deg > b->deg ? a->deg : b->deg;
    int range = newDeg - abs(a->deg - b->deg);
    struct Polynomial* n = makePolynomial(newDeg);
    for (int i = range; i >= 0; i--)
        n->coeff[i] = a->coeff[i] + b->coeff[i];
    if (a->deg > b->deg)
        for (int i = newDeg; i > range; i--)
            n->coeff[i] = a->coeff[i];
    else
        for (int i = newDeg; i > range; i--)
            n->coeff[i] = b->coeff[i];
    findDeg(n);
    return n;
}

struct Polynomial* substractPolynomials(struct Polynomial* a, struct Polynomial* b) {
    int newDeg = a->deg > b->deg ? a->deg : b->deg;
    int range = newDeg - abs(a->deg - b->deg);
    struct Polynomial* n = makePolynomial(newDeg);
    for (int i = range; i >= 0; i--)
        n->coeff[i] = a->coeff[i] - b->coeff[i];
    if (a->deg > b->deg)
        for (int i = newDeg; i > range; i--)
            n->coeff[i] = a->coeff[i];
    else
        for (int i = newDeg; i > range; i--)
            n->coeff[i] = -b->coeff[i];
    findDeg(n);
    return n;
}

struct Polynomial* multiplyPolynomials(struct Polynomial* a, struct Polynomial* b) {
    struct Polynomial* n = makePolynomial(a->deg + b->deg);
    for (int i = 0; i < a->deg + 1; i++)
        for (int j = 0; j < b->deg + 1; j++)
            n->coeff[i + j] += a->coeff[i] * b->coeff[j];
    return n;
}

struct Polynomial* dividePolynomials(struct Polynomial* a, struct Polynomial* b, struct Polynomial* r) {
    struct Polynomial* q = makePolynomial(a->deg < b->deg ? 0 : a->deg);
    if (q->deg == 0) {
        q->coeff[0] = 0.0;
        r->deg = a->deg;
        for(int i = r->deg; i >= 0; i--)
           r->coeff[i] = a->coeff[i];
        return q;
    }
    struct Polynomial* temp = makePolynomial(a->deg);
    for (int i = 0; i < a->deg + 1; i++) {
        temp->coeff[i] = a->coeff[i];
        q->coeff[i] = 0.0;
    }
    for (int i = a->deg - b->deg; i >= 0; i--) {
        q->coeff[i] = temp->coeff[b->deg + i] / b->coeff[b->deg];
        for (int j = b->deg + i - 1; j >= i; j--)
            temp->coeff[j] -= q->coeff[i] * b->coeff[j - i];
    }
    for (int i = 0; i < b->deg; i++) {
        r->coeff[i] = temp->coeff[i];
    }
    if (r->deg < a->deg)
        for (int i = b->deg; i < r->deg + 1; i++)
            r->coeff[i] = 0.0;
    else
        for (int i = b->deg; i < a->deg + 1; i++)
            r->coeff[i] = 0.0;
    free(temp->coeff);
    free(temp);
    findDeg(r);
    findDeg(q);
    return q;
}