【PAT】甲级1009 - Product of Polynomials（多项式乘法）

#include<queue>
#include<cmath>
#include<stack>
#include<cstdio>
#include<vector>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long LL;
#define INF 0x3f3f3f3f
#define CLR(a,b) memset(a,b,sizeof(a))
#define PI acos(-1.0)
#define fi first
#define se second
int main()
{
    int n,k;
    double m;
    double p[2000+5] = {0};     //最大项的次数为2000
    vector<pair<double,int> > a;
    vector<pair<double,int> > b;
    cin >> n;
    while (n--)
    {
        cin >> k >> m;
        a.push_back(make_pair(m,k));
    }
    cin >> n;
    while (n--)
    {
        cin >> k >> m;
        b.push_back(make_pair(m,k));
    }
    for (int i = 0 ; i < a.size() ; i++)
    {
        for (int j = 0 ; j < b.size() ; j++)
        {
            p[a[i].se + b[j].se] += a[i].fi * b[j].fi;
        }
    }
    a.clear();
    for (int i = 2000 ; i >= 0 ; i--)
    {
        if (fabs(p[i]) >= 0.05)
        {
            a.push_back(make_pair(p[i],i));
        }
    }
    cout << a.size();
    for (int i = 0 ; i < a.size() ; i++)
        printf (" %d %.1lf",a[i].se,a[i].fi);
    cout << endl;
    return 0;
}