結果

問題 No.1009 面積の求め方
コンテスト
ユーザー otamay6
提出日時 2020-01-02 14:20:44
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 2 ms / 2,000 ms
コード長 4,315 bytes
コンパイル時間 1,486 ms
コンパイル使用メモリ 169,028 KB
実行使用メモリ 6,820 KB
最終ジャッジ日時 2024-11-22 18:13:06
合計ジャッジ時間 2,298 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 16
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
#define REP(i,n) for(int i=0,i##_len=int(n);i<i##_len;++i)
#define rep(i,a,b) for(int i=int(a);i<int(b);++i)
#define All(x) (x).begin(),(x).end()
#define rAll(x) (x).rbegin(),(x).rend()
using namespace std;
using ll = long long;
template<typename T>
class Polynomial{//f(x)=a_0+a_1x+a_1x^2+...
    std::vector<T> fx;
  public:
    Polynomial(const std::vector<T> &fx={T(1)}):fx(fx){}
    T operator[](size_t k)const{return fx[k];}
    size_t size()const{return fx.size();}
    size_t dim()const{return fx.size()-1;}
    T back()const{return fx.back();}
    Polynomial operator=(const Polynomial &gx){
        fx.resize(gx.size());
        for(int i=0;i<fx.size();++i){
            fx[i]=gx[i];
        }
        return *this;
    }

    Polynomial operator+(const Polynomial &gx)const{
        size_t fs=std::max(fx.size(),gx.size());
        std::vector<T> hx(fs,T(0));
        for(int i=0;i<fs;++i){
            if(i<fx.size()) hx[i]+=fx[i];
            if(i<gx.size()) hx[i]+=gx[i];
        }
        return Polynomial(hx);
    }
    Polynomial operator-(const Polynomial &gx)const{
        size_t fs=std::max(fx.size(),gx.size());
        std::vector<T> hx(fs,T(0));
        for(int i=0;i<fs;++i){
            if(i<fx.size()) hx[i]+=fx[i];
            if(i<gx.size()) hx[i]-=gx[i];
        }
        return Polynomial(hx);
    }
    Polynomial operator*(const Polynomial &gx)const{
        size_t fs=dim()+gx.size();
        std::vector<T> hx(fs,T(0));
        for(int i=0;i<fx.size();++i){
            for(int j=0;j<gx.size();++j){
                hx[i+j]+=fx[i]*gx[j];
            }
        }
        return Polynomial(hx);
    }
    Polynomial operator/(const Polynomial &gx)const{
        std::vector<T> hx=fx;
        std::stack<T> st;
        while(hx.size()>=gx.size()){
            T t=hx.back()/gx.back();
            size_t n=hx.size()-gx.size();
            hx.pop_back();
            for(int i=0;i<gx.size()-1;++i){
                hx[i+n]-=t*gx[i];
            }
            st.push(t);
        }
        hx.clear();
        while(!st.empty()){
            hx.push_back(st.top());
            st.pop();
        }
        return Polynomial(hx);
    }
    Polynomial operator%(const Polynomial &gx)const{
        std::vector<T> hx=fx;
        while(hx.size()>=gx.size()){
            T t=hx.back()/gx.back();
            size_t n=hx.size()-gx.size();
            hx.pop_back();
            for(int i=0;i<gx.size()-1;++i){
                hx[i+n]-=t*gx[i];
            }
        }
        return Polynomial(hx);
    }
    Polynomial operator*(const T &x){
        for(int i=0;i<fx.size();++i){
            fx[i]*=x;
        }
        return *this;
    }
    Polynomial operator+=(const Polynomial &gx){*this=*this+gx;return *this;}
    Polynomial operator-=(const Polynomial &gx){*this=*this-gx;return *this;}
    Polynomial operator*=(const Polynomial &gx){*this=(*this)*gx;return *this;}
    Polynomial operator/=(const Polynomial &gx){*this=*this/gx;return *this;}
    Polynomial operator%=(const Polynomial &gx){*this=*this%gx;return *this;}

    T operator()(const T &x)const{
        if(fx.size()==0) return 0;
        if(fx.size()==1) return x; 
        T f=fx.back();
        for(int i=fx.size()-2;i>=0;--i){
            f=f*x+fx[i];
        }
        return f;
    }
    Polynomial integrate(){
        fx.push_back(0);
        for(int i=fx.size()-1;i>0;--i){
            fx[i]=fx[i-1]/i;
        }
        fx[0]=0;
        return *this;
    }
    Polynomial differencial(){
        for(int i=0;i+1<fx.size();++i){
            fx[i]=(i+1)*fx[i+1];
        }
        fx.pop_back();
        return *this;
    }
    T cintegrate(const T &a,const T &b)const{
        if(fx.size()<=1) return 0;
        T d=fx.back()/size(),u=fx.back()/size();
        for(int i=fx.size()-1;i>0;--i){
            d=d*a+fx[i-1]/i;
            u=u*b+fx[i-1]/i;
        }
        d*=a;
        u*=b;
        return u-d;
    }
    friend std::ostream& operator<<(std::ostream &os, const Polynomial &gx){
        for(int i=0;i<gx.size();++i){
            os << gx[i] << "x^" <<i;
            if(i!=gx.dim()) os<<" + ";
        }
        return os;
    }
};
int main(){
    int a,b;
    cin>>a>>b;
    Polynomial<double> f({(double)a*b,(double)-a-b,1});
    printf("%.16f",-f.cintegrate(a,b));
}
0