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

#define MAX_TERMS 100

typedef struct {
    float coef;
    int expon;
} polynomial;

polynomial terms[MAX_TERMS];
int avail = 0;

int COMPARE(int a, int b)
{
    if (a < b)
        return -1;
    if (a == b)
        return 0;
    else
        return 1;
}

void attach(float coefficient, int exponent)
{
    if (avail >= MAX_TERMS) {
        fprintf(stderr, "Too many terms in the polynomial\n");
        exit(1);
    }
    terms[avail].coef = coefficient;
    terms[avail++].expon = exponent;
}

/* sort terms[start..finish] in DESCENDING order of exponent */
void sort_poly(int start, int finish)
{
    int i, j;
    polynomial temp;
    for (i = start; i < finish; i++) {
        for (j = i + 1; j <= finish; j++) {
            if (terms[i].expon < terms[j].expon) {
                temp = terms[i];
                terms[i] = terms[j];
                terms[j] = temp;
            }
        }
    }
}

void padd(int starta, int finisha, int startb, int finishb,
          int *startd, int *finishd)
{
    float coefficient;
    *startd = avail;

    while (starta <= finisha && startb <= finishb) {
        switch (COMPARE(terms[starta].expon, terms[startb].expon)) {
            case -1:
                attach(terms[startb].coef, terms[startb].expon);
                startb++;
                break;
            case 0:
                coefficient = terms[starta].coef + terms[startb].coef;
                if (coefficient) {
                    attach(coefficient, terms[starta].expon);
                }
                starta++;
                startb++;
                break;
            case 1:
                attach(terms[starta].coef, terms[starta].expon);
                starta++;
                break;
        }
    }

    for (; starta <= finisha; starta++)
        attach(terms[starta].coef, terms[starta].expon);
    for (; startb <= finishb; startb++)
        attach(terms[startb].coef, terms[startb].expon);

    *finishd = avail - 1;
}

int main(void)
{
    int i, j, ae, be, nA, nB, sa, sb, fa, fb, sc, fc = 0;
    int *sd, *fd;
    float ac, bc;

    printf("Enter number of terms in Polynomial A: ");
    scanf("%d", &nA);

    printf("Enter terms for A (coefficient exponent), in ANY order:\n");
    for (i = 0; i < nA; i++) {
        printf("A[%d]: ", i + 1);
        scanf("%f%d", &ac, &ae);
        attach(ac, ae);
    }

    fa = avail - 1;   // A ends here

    sb = avail;
    printf("\nEnter number of terms in Polynomial B: ");
    scanf("%d", &nB);

    printf("Enter terms for B (coefficient exponent), in ANY order:\n");
    for (i = 0; i < nB; i++) {
        printf("B[%d]: ", i + 1);
        scanf("%f%d", &bc, &be);
        attach(bc, be);
    }
    fb = avail - 1;   // B ends here

    // sort A and B by exponent so padd works correctly
    sort_poly(0, fa);
    sort_poly(sb, fb);

    printf("\n-----------------------------------------\n");
    printf("Polynomial A: ");
    for (i = 0; i < nA; i++) {
        printf("%.2fx^%d", terms[i].coef, terms[i].expon);
        if (i < nA - 1) printf(" + ");
    }

    printf("\nPolynomial B: ");
    for (i = sb; i <= fb; i++) {
        printf("%.2fx^%d", terms[i].coef, terms[i].expon);
        if (i < fb) printf(" + ");
    }
    printf("\n-----------------------------------------\n");

    sa = 0;
    sc = avail;
    sd = &sc;
    fd = &fc;

    padd(sa, fa, sb, fb, sd, fd);

    printf("Result (A + B): ");
    for (j = sc; j <= fc; j++) {
        printf("%.2fx^%d", terms[j].coef, terms[j].expon);
        if (j < fc) printf(" + ");
    }
    printf("\n-----------------------------------------\n");

    return 0;
}