SRM 586 Div2 Medium PiecewiseLinearFunctionDiv2

問題

SRM 586 - TopCoder Wiki

2次元上の線分リストが与えられた時に,y座標がある値を取る回数を求める問題.

解答

線分の始点(x, y1)と終点(x+1, y2)が与えられているので与えられた値がmin(y1, y2)とmax(y1, y2)の間にあるかどうかを判定すれば良い.

using namespace std;

class PiecewiseLinearFunctionDiv2
{
public:
  vector <int> countSolutions(vector <int> Y, vector <int> query)
    {
      int n = query.size();
      int m = Y.size();
      vector<int> res;
      int i, j;
      for (i = 0; i < n; i++) {
        int count = 0;
        bool infinite = false;
        bool prev_boundary = false;
        for (j = 0; j < m-1; j++) {
          if (min(Y[j], Y[j+1]) <= query [i] &&
              query[i] <= max(Y[j], Y[j+1])){
            if (Y[j] == Y[j+1]) infinite = true;
            if (!prev_boundary) count++;
            if (query[i] == Y[j+1]) prev_boundary = true;
            else prev_boundary = false;
          }
        }
        if (infinite) res.push_back(-1);
        else res.push_back(count);
      }
      return res;
    }
};