1002. A+B for Polynomials

1002. A+B for 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

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

For each test case you should output the sum 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 to 1 decimal place.

Sample Input

2 1 2.4 0 3.2
2 2 1.5 1 0.5

Sample Output

3 2 1.5 1 2.9 0 3.2

  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 int main()
 17 {
 18 
 19 
 20 
 21     map< double , double > poly1;
 22     map< double , double > poly2;
 23 
 24     set<double> term;
 25 
 26     int n1;    
 27     int n2;
 28 
 29     while( cin >> n1 )
 30     {
 31 
 32         poly1.clear();
 33         poly2.clear();
 34         term.clear();
 35 
 36 
 37         for( int i = 0 ; i < n1 ; ++i )
 38         {
 39             double exp;
 40             double coe;
 41 
 42             cin >> exp;
 43             cin >> coe;
 44 
 45             if( coe != 0 )
 46             {
 47                 term.insert(exp);
 48 
 49                 poly1[exp] = coe;
 50             }
 51 
 52         }
 53 
 54         cin >> n2;
 55 
 56         for( int i = 0 ; i < n2 ; ++i )
 57         {
 58             double exp;
 59             double coe;
 60 
 61             cin >> exp;
 62             cin >> coe;
 63 
 64 
 65 
 66             if( coe != 0 )
 67             {
 68 
 69                 term.insert(exp);
 70 
 71                 poly2[exp] = coe;
 72             }
 73 
 74         }
 75 
 76 
 77         set<double>::reverse_iterator rit;
 78         vector<double> to_delete;
 79         to_delete.clear();
 80 
 81         for( rit = term.rbegin() ; rit != term.rend() ; ++rit )
 82         {
 83 
 84             double c1;
 85             double c2;
 86 
 87             map<double,double>::iterator it;
 88 
 89             it = poly1.find(*rit);
 90 
 91             if( it!= poly1.end() )
 92             {
 93                 c1 = it->second;
 94             }
 95             else
 96             {
 97                 c1 = 0;
 98             }
 99 
100             it = poly2.find(*rit);
101 
102             if( it!= poly2.end() )
103             {
104                 c2 = it->second;
105             }
106             else
107             {
108                 c2 = 0;
109             }
110 
111             if( c1 + c2 == 0 )
112             {
113                 to_delete.push_back(*rit);
114             }
115 
116         }
117 
118 
119 
120         for( int i = 0 ; i < to_delete.size() ; ++i )
121         {
122             term.erase(to_delete[i]);
123         }
124 
125         cout << term.size();
126 
127 
128 
129         for( rit = term.rbegin() ; rit != term.rend() ; ++rit )
130         {
131             printf(" %.0f" , *rit );
132 
133             double c1;
134             double c2;
135 
136             map<double,double>::iterator it;
137 
138             it = poly1.find(*rit);
139 
140             if( it!= poly1.end() )
141             {
142                 c1 = it->second;
143             }
144             else
145             {
146                 c1 = 0;
147             }
148 
149             it = poly2.find(*rit);
150 
151             if( it!= poly2.end() )
152             {
153                 c2 = it->second;
154             }
155             else
156             {
157                 c2 = 0;
158             }
159 
160             double coe = c1 + c2;
161 
162 
163             printf(" %.1f" , coe);
164 
165 
166 
167         }
168         cout << endl;
169     }
170 
171 
172 
173 
174 
175 
176 
177 
178     return 0;
179 }