/************************************************
Grundlegende Algorithmen mit Java,
http://algorithmen-und-problemloesungen.de/
Copyright @2007-2009 by Doina Logofatu

in C#: Michael Gärtner
************************************************/

using System;
using System.Collections.Generic;
using System.IO;

namespace Logofatu
{
    class P07Fourier
    {
        private static String FileInputName = "fourier.in";
        private static String FileOutputName = "fourier.out";
        private static IFormatProvider formatProvider =
            System.Globalization.CultureInfo.GetCultureInfo("en-US").NumberFormat;

        private static List<Complex> fft(List<Complex> a)
        {
            int n = a.Count;
            if ( n <= 1 )
                return a;
            Complex wn = new Complex(Math.Cos(2 * Math.PI / n), Math.Sin(2 * Math.PI / n));
            Complex w = new Complex(1.0, 0.0);
            List<Complex> a0 = new List<Complex>();
            List<Complex> a1 = new List<Complex>();
            List<Complex> y = new List<Complex>();
            for ( int i = 0; i < n; i++ )
            {
                Complex c = a[i];
                if ( i % 2 == 0 )
                    a0.Add(c);
                else
                    a1.Add(c);
                y.Add(new Complex(0, 0));
            }
            List<Complex> y0 = fft(a0);
            List<Complex> y1 = fft(a1);
            for ( int i = 0; i < n / 2; i++ )
            {
                Complex aux = w.mulitply(y1[i]);
                y[i] = y0[i].add(aux);
                y[i + n / 2] = y0[i].substract(aux);
                w = w.mulitply(wn);
            }
            return y;
        }

        static void Main(string[] args)
        {
            StreamReader sr = null;
            StreamWriter sw = null;
            try
            {
                sw = new StreamWriter(FileOutputName);
                sr = new StreamReader(FileInputName);
                List<Complex> a = new List<Complex>();
                while ( !sr.EndOfStream )
                {
                    string[] sArray = sr.ReadLine().Split(' ');
                    double re = double.Parse(sArray[0], formatProvider);
                    double im = double.Parse(sArray[1], formatProvider);
                    a.Add(new Complex(re, im));
                }
                List<Complex> y = fft(a);
                foreach ( Complex c in y )
                {
                    sw.WriteLine(c.toString("G6", formatProvider));
                }
            }
            catch ( IOException ex )
            {
                Console.Write("Fehler bei der Dateiverarbeitung!\n" + ex);
            }
            finally
            {
                if ( sr != null )
                {
                    sr.Close();
                }
                if ( sw != null )
                {
                    sw.Close();
                }
            }
        }
    }

    class Complex
    {
        private double re, im;

        public Complex()
            : this(0, 0)
        {
        }
        public Complex(double newRe, double newIm)
        {
            re = newRe;
            im = newIm;
        }

        public string toString(string format, IFormatProvider formatProvider)
        {
            return this.re.ToString(format,formatProvider) + "  " +
                this.im.ToString(format,formatProvider);
        }

        public Complex add(Complex z)
        {
            return new Complex(re + z.re, im + z.im);
        }

        public Complex substract(Complex z)
        {
            return new Complex(re - z.re, im - z.im);
        }

        public Complex mulitply(Complex z)
        {
            return new Complex(re * z.re - im * z.im, re * z.im + im * z.re);
        }
    }
}