﻿PAT(A) 1009. Product of Polynomials (25)-Ocrosoft

# PAT(A) 1009. Product of Polynomials (25)

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 aN1 N2 aN2 … NK aNK, where K is the number of nonzero terms in the polynomial, Ni and aNi (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
```

```#include <set>
#include <map>
#include <list>
#include <cmath>
#include <stack>
#include <queue>
#include <ctime>
#include <string>
#include <cstdio>
#include <vector>
#include <cctype>
#include <climits>
#include <sstream>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <functional>
#define strend string::npos
#define ms(a) memset(a,0,sizeof(a))
#define  rep(a,v,b) for(int a=v;a<b;a++)
#define  repe(a,v,b) for(int a=v;a<=b;a++)
typedef long long LL;
const LL LINF = LLONG_MAX / 2;
const int INF = INT_MAX / 2;
const int MAXN = 2000 + 10;
const int MOD = 1000000009;
LL GCD(LL a, LL b)
{
if (!b)return a;
return GCD(b, a%b);
}
/*(◕‿‿◕) (◕‿‿◕) (◕‿‿◕) (◕‿‿◕) (◕‿‿◕)*/
/*(◕‿‿◕) 签订契约，成为马猴烧酒吧! (◕‿‿◕)*/
/*(◕‿‿◕) (◕‿‿◕) (◕‿‿◕) (◕‿‿◕) (◕‿‿◕)*/
using namespace std;
int main()
{
map<int, double,greater<int> > x, x1, x2;
x.clear(); x1.clear(); x2.clear();
int n; cin >> n;
for (int i = 0; i < n; i++)
{
int t; double y;
cin >> t >> y;
x1[t] = y;
}
cin >> n;
for (int i = 0; i < n; i++)
{
int t; double y;
cin >> t >> y;
x2[t] = y;
}
map<int, double,greater<int> >::iterator i, j;
for (i = x1.begin(); i != x1.end(); i++)
{
for (j = x2.begin(); j != x2.end(); j++)
{
if (x.count(i->first + j->first))x[i->first + j->first] += i->second*j->second;
else x[i->first + j->first] = i->second*j->second;
}
}
int sum = 0;
for (i = x.begin(); i != x.end(); i++)
if (i->second)sum++;
printf("%d", sum);
for (i = x.begin(); i != x.end(); i++)
if (i->second)printf(" %d %.1lf", i->first, i->second);
printf("\n");
return 0;
}```