SRM586 Div1 Easy

250

class PiecewiseLinearFunction {
public:
  int maximumSolutions(vector <int> Y)
  {
    vector<double> v;
    for (int i = 0; i < Y.size(); ++i) {
      v.push_back(Y[i]);
    }

    for (int i = 0; i + 1 < v.size(); ++i) {
      if (v[i] == v[i + 1]) return -1;
    }

    vector<double> cand;
    for (int i = 0; i < v.size(); ++i) {
      cand.push_back(v[i]);
      for (int j = i + 1; j < v.size(); ++j) {
        cand.push_back((v[i] + v[j]) / 2.0);
      }
    }

    int ret = -1;

    for (int i = 0; i < cand.size(); ++i) {
      double c = cand[i];
      int cnt = 0;
      for (int j = 0; j + 1 < v.size(); ++j) {
        double mx = max(v[j], v[j + 1]);
        double mn = min(v[j], v[j + 1]);
        if (mn <= c && c <= mx) ++cnt;
      }
      for (int j = 1; j + 1 < v.size(); ++j) {
        if (v[j] == c) --cnt;
      }
      if (0 < cnt) ret = max(ret, cnt);
    }

    return ret;
  }