#include <complex>
#include <vector>


using namespace std;

typedef complex<double> cdouble;

const double PI2  = 2 * 3.141593654;

vector<cdouble> fft(const vector<double>& input)
{
	int N = input.size();

	vector<cdouble> output(N);

	for (int k=0; k<N; k++)
	{
		cdouble out_val(0,0);

		for(int n=0; n<N; n++)
		{
			out_val += cdouble(input[n],0.0) * cdouble(cos( (PI2 * k * n) / N ), sin( (PI2 * k * n) / N ));
		}

		output[k] = out_val;
	}
	return output;
}

vector<cdouble> fft(const vector<double>& input, int N)
{
	vector<cdouble> output(N);

	for (int k=0; k<N; k++)
	{
		cdouble out_val(0,0);

		for(int n=0; n<input.size(); n++)
		{
			out_val += cdouble(input[n],0.0) * cdouble(cos( (PI2 * k * n) / N ), sin( (PI2 * k * n) / N ));
		}

		output[k] = out_val;
	}
	return output;
}