fftconv.cpp

#include <bits/stdc++.h>
using namespace std;
#define loop(i,n)      for(int i = 0; i < (n); i++)
#define loopA(i,a,n)  for(int i = a; i <= (n); i++)
#define loopD(i,a,n)  for(int i = a; i >= (n); i--)
#define endl "\n"
#define mp make_pair
#define pb push_back
#define pi 3.14159265358979
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef vector<int> vi;
void DFT(complex<double>* a, int N){
    if(N<=1){
        return;
    }
    else{
        int k = N/2;
        complex<double>* yl = NULL, *yr = NULL;
        yl = new complex<double>[k];yr = new complex<double>[k];
        loop(i,k){
            yl[i] = a[2*i];
            yr[i] = a[2*i+1];
        }
        DFT(yl,k);
        DFT(yr,k);
        // complex<double> w(1.0,0.0), k = polar(1.0,2*pi/(double)N);
        loop(i,k){
            complex<double> w = polar(1.0, ((double)pi*i)/k);
            a[i] = yl[i] + w*yr[i];
            a[k+i] = yl[i] - w*yr[i];
            // w = w*k;
        }
        delete [] yl;
        delete [] yr;
    }
}

void iDFT(complex<double>* a, int N){
    if(N<=1){
        return;
    }
    else{
        int k = N/2;
        complex<double>* yl = NULL, *yr = NULL;
        yl = new complex<double>[k];yr = new complex<double>[k];
        loop(i,k){
            yl[i] = a[2*i];
            yr[i] = a[2*i+1];
        }
        iDFT(yl,k);
        iDFT(yr,k);
        // complex<double> w(1.0,0.0), k = polar(1.0,-2*pi/(double)N);
        loop(i,k){
            complex<double> w = polar(1.0, (-(double)pi*i)/k);
            a[i] = yl[i] + w*yr[i];
            a[k+i] = yl[i] - w*yr[i];
            // w = w*k;
        }
        delete [] yl;
        delete [] yr;
    }
}


int main(){
    ios_base::sync_with_stdio(false);cin.tie(NULL);
    cout<<std::fixed<<std::setprecision(3);
    // #ifndef ONLINE_JUDGE
    //     // for getting input from input.txt
    //     freopen("input.txt", "r", stdin);
    //     // for writing output to output.txt
    //     freopen("output.txt", "w", stdout);
    // #endif
    int t;
    cin>>t;
    while(t--){
        int n;cin>>n;
        int N = 1;
        while(N<2*n)N*=2;
        // cout<<N<<endl;
        complex<double> v1[N],v2[N],result[N];
        // cout<<k_fft<<"dvjksdbfv"<<k_ifft<<endl;
        loop(i,n){
            double a,b;cin>>a>>b;
            v1[i] = complex<double> (a,b);
        }
        loop(i,n){
            double a,b;cin>>a>>b;
            v2[i] = complex<double> (a,b);
        }
        loopA(i,n,N-1){
            v1[i] = complex<double> (0.0,0.0);
            v2[i] = complex<double> (0.0,0.0);
        }
        
        DFT(v1,N);DFT(v2,N);
        loop(i,N){
            result[i] = v1[i]*v2[i];
            // result[i] = conj(result[i]);
        }
        iDFT(result, N);
        loop(i, N){
            // result[i] = conj(result[i]);
            double a = real(result[i])/(double)N, b = imag(result[i])/(double)N;
            if(a<0.001&&a>-0.001)a = 0.0;
            if(b<0.001&&b>-0.001)b = 0.0;
            result[i] = complex<double> (a,b);
        }
        loop(i, N)cout<<result[i]<<endl;
    }
    return 0;
}