Product of Polynomials

题意：多项式相乘，合并同类项后输出每一项的系数。

题目链接：https://www.patest.cn/contests/pat-a-practise/1009

分析：注意合并后系数为0，这一项就不存在了。

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1000 + 10;
const int MAXT = 2000 + 10;
map<int, double> mp1;
map<int, double> mp2;
map<int, double> mp3;
stack<pair<int, double> > st;
int main(){
    int n;
    scanf("%d", &n);
    int id;
    double x;
    while(n--){
        scanf("%d%lf", &id, &x);
        mp1[id] = x;
    }
    scanf("%d", &n);
    while(n--){
        scanf("%d%lf", &id, &x);
        mp2[id] = x;
    }
    for(map<int, double>::iterator it1 = mp1.begin(); it1 != mp1.end(); ++it1){
        for(map<int, double>::iterator it2 = mp2.begin(); it2 != mp2.end(); ++it2){
            id = (*it1).first + (*it2).first;
            mp3[id] += (*it1).second * (*it2).second;
        }
    }
    for(map<int, double>::iterator it = mp3.begin(); it != mp3.end(); ++it){
        if((*it).second == 0) continue;
        st.push(pair<int, double>((*it).first, (*it).second));
    }
    printf("%d", st.size());
    while(!st.empty()){
        pair<int, double> tmp = st.top();
        st.pop();
        printf(" %d %.1lf", tmp.first, tmp.second);
    }
    printf("
");
    return 0;
}