# include < iostream >
# include < fstream >
struct Term {
int coeff ;
int power ;
Term * next ;
};
Term * create_term ( int coeff , int power ) {
Term * new_term = new Term ;
new_term -> coeff = coeff ;
new_term -> power = power ;
new_term -> next = nullptr ;
return new_term ;
}
void insert_term ( Term *& head , int coeff , int power ) {
Term * new_term = create_term ( coeff , power );
if (! head || head -> power < power ) {
new_term -> next = head ;
head = new_term ;
} else {
Term * current = head ;
while ( current -> next && current -> next -> power > power ) {
current = current -> next ;
}
new_term -> next = current -> next ;
current -> next = new_term ;
}
}
Term * multiply_poly ( Term * head1, Term * head2) {
Term * result = nullptr ;
for ( Term * i = head1; i; i = i-> next ) {
for ( Term * j = head2; j; j = j-> next ) {
int coeff = i-> coeff * j-> coeff ;
int power = i-> power + j-> power ;
insert_term ( result , coeff , power );
}
}
return result ;
}
void print_poly ( Term * head ) {
while ( head ) {
std :: cout << head -> coeff << "x^" << head -> power ;
if ( head -> next ) std :: cout << " + " ;
head = head -> next ;
}
std :: cout << std :: endl ;
}
void delete_poly ( Term *& head ) {
while ( head ) {
Term * temp = head ;
head = head -> next ;
delete temp ;
}
}
int main () {
std :: ifstream input_file ( "polinoame.txt" ) ;
Term *head1 = nullptr , *head2 = nullptr ;
int n1, n2, coeff , power ;
input_file >> n1;
for ( int i = 0 ; i < n1; ++i) {
input_file >> coeff >> power ;
insert_term (head1, coeff , power );
}
input_file >> n2;
for ( int i = 0 ; i < n2; ++i) {
input_file >> coeff >> power ;
insert_term (head2, coeff , power );
}
Term * result = multiply_poly (head1, head2);
print_poly ( result );
delete_poly (head1);
delete_poly (head2);
delete_poly ( result );
return 0 ;
}