1009. Product of Polynomials

1009. Product of Polynomials (25)

时间限制

400 ms

内存限制

32000 kB

代码长度限制

16000 B

判题程序

Standard

作者

CHEN, Yue

This time, you are supposed to find A*B where A and B are two polynomials.

Input Specification:

Each input file contains one test case. Each case occupies 2 lines, and each line contains the information of a polynomial: K N1 a_N1 N2 a_N2 ... NK a_NK, where K is the number of nonzero terms in the polynomial, Ni and a_Ni (i=1, 2, ..., K) are the exponents and coefficients, respectively. It is given that 1 <= K <= 10, 0 <= NK < ... < N2 < N1 <=1000.

Output Specification:

For each test case you should output the product of A and B in one line, with the same format as the input. Notice that there must be NO extra space at the end of each line. Please be accurate up to 1 decimal place.

Sample Input

2 1 2.4 0 3.2
2 2 1.5 1 0.5

Sample Output

3 3 3.6 2 6.0 1 1.6

  1 #include <iostream>
  2 #include <fstream>
  3 #include <vector>
  4 #include <string>
  5 #include <algorithm>
  6 #include <map>
  7 #include <stack>
  8 #include <cmath>
  9 #include <queue>
 10 #include <set>
 11 
 12 
 13 using namespace std;
 14 
 15 
 16 class Term
 17 {
 18 public :
 19     int exponent;
 20     double coefficient;
 21 };
 22 
 23 
 24 bool operator< ( const Term &t1 , const Term &t2 )
 25 {
 26     return t1.exponent > t2.exponent;
 27 }
 28 
 29 //bool operator== ( const Term &t1 , const Term &t2 )
 30 //{
 31 //    return t1.exponent == t2.exponent;
 32 //}
 33 
 34 
 35 class Polynomial
 36 {
 37 public :
 38     vector<Term> terms;
 39 
 40     void addTerm( const Term &term )
 41     {
 42 
 43         for( int i = 0 ; i < this->terms.size() ; ++i )
 44         {
 45             if( this->terms[i].exponent == term.exponent )
 46             {
 47                 this->terms[i].coefficient += term.coefficient;
 48                 if( this->terms[i].coefficient == 0 )
 49                 {
 50                     this->terms.erase(this->terms.begin() + i);
 51                 }
 52                 return;
 53             }
 54         }
 55 
 56         this->terms.push_back(term);
 57 
 58     }
 59 
 60 
 61     Polynomial times( const Polynomial &poly )
 62     {
 63         Polynomial result;
 64 
 65         for( int i = 0 ; i < poly.terms.size() ; ++i )
 66         {
 67             for( int j = 0 ; j < this->terms.size() ; ++j )
 68             {
 69                 Term term;
 70                 term.exponent = this->terms[j].exponent + poly.terms[i].exponent;
 71                 term.coefficient = this->terms[j].coefficient * poly.terms[i].coefficient;
 72 
 73                 result.addTerm(term);
 74             }
 75         }
 76 
 77         return result;
 78     }
 79 
 80 
 81 
 82     void toString()
 83     {
 84 
 85 
 86         sort(this->terms.begin() , this->terms.end());
 87     
 88         printf("%d" , this->terms.size());
 89 
 90         for( int i = 0 ; i < this->terms.size() ; ++i )
 91         {
 92             printf( " %d %.1f" , this->terms[i].exponent , this->terms[i].coefficient );
 93         }
 94         
 95         cout << endl;
 96     }
 97 };
 98 
 99 
100 
101 
102 int main()
103 {
104 
105 
106 
107     Polynomial p1;
108     Polynomial p2;
109     int n;
110     int m;
111 
112     cin >> n;
113     
114     for( int i = 0 ; i < n ; ++i )
115     {
116         Term term;
117         
118         cin >> term.exponent >> term.coefficient;
119 
120         p1.addTerm(term);
121     }
122 
123     cin >> m;
124 
125     for( int i = 0 ; i < m ; ++i )
126     {
127         Term term;
128         
129         cin >> term.exponent >> term.coefficient;
130 
131         p2.addTerm(term);
132     }
133 
134     p1.times(p2).toString();
135 
136     return 0;
137 }