SRM 421 Div2 Medium EquilibriumPoints

問題

N個の地点が直線上に並んでおり,x[i]の地点にm[i]の質量の物体がある.ある2点間にはその距離と質量に応じて重力が発生する(計算式略).入力のN個の物体は重力の影響を受けないが,新たに追加するPは重力の影響を受ける.もし,Pの左側の全ての物体の重力和と,右側の全ての物体の重力和が等しい時,均衡しているという.均衡する地点が必ずN-1個あるので,その地点をソートして返せ.

解答

直感的にx[i]とx[i+1]の間には均衡する地点は高々1つなことが分かる.とするとN-1個の均衡する地点は各地点間に1つずつあると予想.もしも,x[i]とx[i-1]の間の地点Pで左の重力和のほうが小さい場合,均衡点はPよりも左側に,そうでない場合は右側にある.よって,各地点で左側,右側の重力和を求め誤差が許容範囲内に収まるまでバイナリサーチを使えばよい.

double eps = 1e-9;
class EquilibriumPoints
{
public:
  vector <double> getPoints(vector <int> x, vector <int> m)
    {
      int n = x.size();
      vector<double> res;
      for (int i = 1; i < n; i++){
        double low = x[i-1];
        double up = x[i];
        double mid;
        while (1){
          mid = (low+up) / 2;
          if (low+eps >= up) break;
          double sumleft = 0;
          double sumright = 0;
          for(int j = 0; j < i; j++){
            sumleft += m[j]/((mid-x[j]) * (mid-x[j]));
          }
          for(int j = i; j < n; j++){
            sumright += m[j]/((mid-x[j]) * (mid-x[j]));
          }
          if (sumleft < sumright){
            up = mid;
          }else {
            low = mid;
          }
        }
        res.push_back(mid);
      }
      return res;
    }
};