#include <iostream>
#include <vector>
#include <cmath>
#include <fstream>
#include<algorithm>
using namespace std;

class Wielomian
{
public: 
  vector<double> coof; // <- to bedziemy chcieli ukryc z sekcji publicznej

  Wielomian(const vector<double> &tab);
  Wielomian operator*(const Wielomian &a) const;
  Wielomian operator*(double x) const;
  Wielomian pochodna() const;
  Wielomian operator-(const Wielomian &a) const;
  double operator()(double x) const;
  vector<double> roots() const;
  static Wielomian gen(int n);
};

Wielomian::Wielomian(const vector<double> &tab)
{
  coof=tab;
}

Wielomian Wielomian::operator*(double x) const
{
  vector<double> wyn;
  for (auto a:coof)
  {
    wyn.push_back(a*x);
  }
  return Wielomian(wyn);
}
Wielomian Wielomian::pochodna() const
{
  vector<double>wyn;
  for (int i = 1; i < coof.size(); i++) {
    wyn.push_back(i*coof[i]);
  }
  return Wielomian(wyn);
}
double Wielomian::operator()(double x) const
{
  double wyn=0;
  for (int i=0;i<coof.size();i++)
  {
    wyn+=pow(x,i)*coof[i];
  }
  return wyn;
}

ostream& operator<<(ostream &out, const Wielomian &a)
{
  for (auto c:a.coof)
  {
    out<<c<<" "; // mogloby byc ladniej, np. zamiast "5.3 2.1 3" mogloby byc tak: "5.3 x^2 + 2.1 x + 3"
  }
  out<<endl;
  return out;
}

Wielomian Wielomian::operator*(const Wielomian &t) const
{
  vector<double> wyn;
  vector<double> a=coof;
  vector<double> b=t.coof;
  for (int i=0;i<=a.size()+b.size();i++)
  {
    double temp=0;
    for (int j=0;j<i+1;j++)
      {
        if (j>a.size()-1 || i-j>b.size()-1 || i-j<0)
        {
          ;
        }
        else
        {
          temp+=a[j]*b[i-j];
        }
      }
    wyn.push_back(temp);
  }
  while (wyn.back()==0) {
    wyn.pop_back();
  }
  return Wielomian(wyn);
}

Wielomian operator*(double x, const Wielomian &a)
{
  return a*x;
}

vector<double> Wielomian::roots() const
{
  if (coof.size()==0)
  {
    return vector<double>();
  }
  
  if (coof.size()==2)
  {
    return vector<double>( {-coof[0]/coof[1]} );
  }
  // TODO: przypadek funkcji kwadratowej
  
  // zawsze musimy cos zwrocic
  return vector<double>();
}

Wielomian Wielomian::operator-(const Wielomian &a) const
{
  vector<double> wyn;
  for (int i=0;i<max(coof.size(),a.coof.size());i++)
  {
    double x;
    double y;
    if (i>=coof.size())
    {
      x=0;
    }
    else
    {
      x=coof[i];
    }
    if (i>=a.coof.size())
    {
      y=0;
    }
    else
    {
      y=(a.coof)[i];
    }
    wyn.push_back(x-y);
  }
  return Wielomian(wyn);
}

class Czebyszew : public Wielomian
{
  public:
  int n; // <- tego raczej nie powinno byc, a na pewno nie w sekcji publicznej
    Czebyszew (int n): Wielomian(vector<double>())
    {
      if (n==0)
      {
        this->coof=vector<double>{1};
      }
      else if (n==1)
      {
        this->coof=vector<double>{0,1};
      }
      else
      {
        this->coof=(Czebyszew(n-1)*Wielomian(vector<double>{0,2})-Czebyszew(n-2)).coof;
      }
      this->n=n;
    }
    
    
    vector<double> roots() const
    {
      vector<double> wyn;
      for (int i = 0; i < n; i++)
      {
        wyn.push_back(cos( M_PI*(i+1/2)/n));
      }
      return wyn;
    }
};


int main()
{
  vector<double> tab={1,1,1,1,1};
  Wielomian a(tab);
  cout<<a<<a.pochodna();
  cout<<Wielomian({1,2,3})*5;
  cout<<5*Wielomian({1,2,3});
  cout<<Wielomian({1,1,1})-Wielomian({1,1});
  cout<<Wielomian({1,2,3})(0)<<endl;
  cout<<Czebyszew(1);
  cout<<Czebyszew(2);
  cout<<Czebyszew(3);
  cout<<Czebyszew(4);
  cout<<Czebyszew(5);
  cout<<Czebyszew(6);
  cout<<Czebyszew(6).roots();
  return 0;
}