SRM492 Div1 Easy

250
2つの木を切らずに使う様な場合を考える。何故それで正しいかはよく分からない。勘。
計算の順序によっては精度がアレ。サンプルが親切なので、気付かないってことはない。

class TimeTravellingGardener {
public:
  int determineUsage(vector <int> D, vector <int> y)
  {
    vector<int> x;
    x.push_back(0);
    partial_sum(D.begin(), D.end(), back_inserter(x));
   
    int mn = (int)y.size() - 1;

    for (int i = 0; i < (int)x.size(); ++i) {
      for (int j = i+1; j < (int)x.size(); ++j) {
        int cnt = 0;
        for (int k = 0; k < (int)x.size(); ++k) {
          if (i == k || j == k) continue;
          double h = (double)(y[i] - y[j]) * (double)(x[k] - x[i]) / (double)(x[i] - x[j])+ y[i];
          if (h < y[k]) ++cnt

          if (h > y[k]) cnt = 1 << 20;
          if (h < 0.0) cnt = 1 << 20;
        }
        mn = min(mn, cnt);
      }
    }


    return mn;
  }
};