SRM436 Div2 Medium

500

割り算するのが怖いからccw

typedef complex<double> Point;

double cross(Point a, Point b)
{
  return (a.real() * b.imag() - a.imag() * b.real());
}

double dot(Point a, Point b)
{
  return (a.real() * b.real() + a.imag() * b.imag());
}

namespace CCW{
  enum{ RIGHT = 1, LEFT = -1, FRONT = 2, BACK = 2, OTHER = 0 };
};
int ccw(Point a, Point b, Point c)
{
  b -= a;
  c -= a;
  if( cross(b, c) < 0 )return CCW::RIGHT;
  if( cross(b, c) > 0 )return CCW::LEFT;
  if( dot(b, c) < 0 )return CCW::BACK;
  if( norm(b) < norm(c) )return CCW::FRONT;
  return CCW::OTHER;
}

class BestView {
public:
  int numberOfBuildings(vector <int> hs)
  {
    const int N = hs.size();
    if (N == 1) return 0;
    if (N == 2) return 1;

    vector<Point> ps;
    for (int i = 0; i < N; ++i) {
      ps.push_back(Point(i, hs[i]));
    }

    int mx = 0;
    for (int i = 0; i < N; ++i) {
      int cnt = 0;
      if (i) ++cnt;
      for (int j = 0; j < i - 1; ++j) {
        bool flg = true;
        for (int k = j + 1; k < i; ++k) {
          flg = flg && ccw(ps[j], ps[i], ps[k]) == CCW::RIGHT;
        }
        if (flg) ++cnt;
      }
      if (i + 1 < N) ++cnt;
      for (int j = i + 2; j < N; ++j) {
        bool flg = true;
        for (int k = i + 1; k < j; ++k) {
          flg = flg && ccw(ps[i], ps[j], ps[k]) == CCW::RIGHT;
        }
        if (flg) ++cnt;
      }
      mx = max(mx, cnt);
    }

    return mx;
  }
};