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.22 2 1.5 1 0.5

Sample Output

3 3 3.6 2 6.0 1 1.6

#include 
     
      #include 
      
       #include 
       
        #include 
        
         using namespace std;typedef struct Node{  int exp;//指数  float coe;//系数}Node;Node product(Node a,Node b){  a.exp = a.exp+b.exp;  a.coe = a.coe*b.coe;  return a;}bool compare(Node a,Node b){    return a.exp>b.exp;}int main(){  Node node;  int M,N;    vector
         
            vec1,vec2,vec,vec3;  vector
          
           ::iterator it1,it2; cin>>M; while(M--) { cin>>node.exp>>node.coe; vec1.push_back(node); } cin>>N; while(N--) { cin>>node.exp>>node.coe; vec2.push_back(node); } for (it1=vec1.begin();it1!=vec1.end();it1++) for (it2=vec2.begin();it2!=vec2.end();it2++) { Node t = product(*it1,*it2); if (t.coe !=0) vec.push_back(t); } sort(vec.begin(),vec.end(),compare); for (it1=vec.begin();it1!=vec.end();it1 =it2) { for (it2=it1+1;it2!=vec.end() && ((*it1).exp == (*it2).exp);it2++) (*it1).coe +=(*it2).coe; if ((*it1).coe !=0) { vec3.push_back(*it1); } } cout<