SRM635

250は整数問題にしてやるやり方とdoubleでやるやり方がありますが、doubleでやると誤差死します。 無理矢理、doubleで通しました。

Level1

#include <string>
#include <vector>
#include <iostream>
#include <algorithm>
#include <functional>
#include <cmath>
using namespace std;
double eps=0.0000001;
double magic(double x){return(x==0?0:1/x);}
bool dequal(double x,double y){
    return abs(x-y)<eps && abs(magic(x)-magic(y))<eps;
}
class SimilarRatingGraph
{
public:
    double maxLength(vector <int> date, vector <int> rating){
        int N=date.size();
        vector<double> t(N-1);
        for(int i=0;i<N-1;i++)
            t[i]=date[i+1]-date[i];
        vector<double> k(N-1);
        for(int i=0;i<N-1;i++)
            k[i]=(rating[i+1]-rating[i])/t[i];
        vector<double> L(N-1);
        for(int i=0;i<N-1;i++)
            L[i]=sqrt(1+k[i]*k[i])*t[i];

        double maxL=0;
        for(int i=0;i<N-1;i++)
            for(int j=i+1;j<N-1;j++){
                double s=(t[i])/(t[j]);
                double sum=0;
                for(int l=0;l<N-j-1;l++){
                    if(dequal(k[i+l],k[j+l])&& dequal(t[i+l],t[j+l]*s)){
                        sum+=max(L[i+l],L[j+l]);
                        maxL=max(maxL,sum);
                    }else break;
                }
            }
        return maxL;
    }
};