EquilibriumPoints.cpp

class EquilibriumPoints {
    public:
    vector<double> getPoints(vector<int> x, vector<int> m) {
        vector<double> ret;
        for(int i = 0;i < x.size() - 1; ++ i){
            double lo = x[i], hi = x[i+1];
            while(hi - lo > 1e-9){ // bug: why > EPS. because we need to keep search if > EPS
                double mid = (hi + lo) / 2;
                double F = 0; // trick: use negative for left force
                for(int j = 0; j <= i; ++ j){
                    F -= m[j] / (mid-x[j]) / (mid-x[j]); // trick: use /x/x for /(x*x)
                }
                for(int j = i+1; j < x.size(); ++ j){
                    F += m[j] / (x[j]-mid) / (x[j]-mid);
                }
                if(F>0){
                    hi=mid;
                }
                else{
                    lo=mid;
                }
            }
            ret.push_back((hi+lo)/2.0);
        }
        return ret;
    }
};