#include <vector>
#include <complex>
#include <iostream>
using namespace std;
#include <cmath>

#define M_PI 3.14159265358979323846

int main()
{
	
}

vector<complex<double>> FFT(vector<complex<double>>& samples)
{
	int N = samples.size();
	if (N == 1) return samples;
	int M = N / 2;
	vector<complex<double>> Xeven(M, 0);
	vector<complex<double>> Xodd(M, 0);
	for (int i = 0; i != M; i++)
	{
		Xeven[i] = samples[2 * i];
		Xodd[i] = samples[2 * i + 1];
	}
	vector<complex<double>> Feven(M, 0);
	Feven = FFT(Xeven);
	vector<complex<double>> Fodd(M, 0);
	Fodd = FFT(Xodd);
	vector<complex<double>> freqbins(N, 0);
	for (int k = 0; k != N / 2; k++)
	{
		complex<double> cmplxexponential = polar(1.0, -2 * M_PI * k / N)*Fodd[k];
		freqbins[k] = Feven[k] + cmplxexponential;
		freqbins[k + N / 2] = Feven[k] - cmplxexponential;
	}
	return freqbins;
}