TrianglesContainOriginEasy.cpp

struct point
{
    point() : x(0), y(0) { }
    point(double x_, double y_) : x(x_), y(y_) { }
    double x, y;
};
point operator-(const point& a, const point& b) { return point(a.x - b.x, a.y - b.y); }
point operator+(const point& a, const point& b) { return point(a.x + b.x, a.y + b.y); }

typedef point vector2d;

// 外積を求める
double cross(const vector2d& a, const vector2d& b)
{
    return a.x * b.y - a.y * b.x;
}

// 点 p が反時計回りの三角形 abc の内側にあるかどうか判定
bool point_in_triangle(const point& p, const point& a, const point& b, const point& c)
{
    // p が ab の右側にあれば三角形の外側にある
    if (cross(p - a, b - a) < 0.0) return false;
    // p が bc の右側にあれば三角形の外側にある
    if (cross(p - b, c - b) < 0.0) return false;
    // p が ca の右側にあれば三角形の外側にある
    if (cross(p - c, a - c) < 0.0) return false;
    return true;
}


class TrianglesContainOriginEasy {
    public:
    int count(vector<int> x, vector<int> y) {
      int ans=0;

      for(int i=0;i<x.size();i++)
        for(int j=i+1;j<x.size();j++)
          for(int k=j+1;k<x.size();k++)
            {

              if(point_in_triangle(point(0,0),point(x[i],y[i]), point(x[j],y[j])
                                   , point(x[k],y[k]))||
                 point_in_triangle(point(0,0),point(x[i],y[i]), point(x[k],y[k])
                                   , point(x[j],y[j]))||
                 point_in_triangle(point(0,0),point(x[j],y[j]), point(x[i],y[i])
                                   , point(x[j],y[j]))||
                 point_in_triangle(point(0,0),point(x[j],y[j]), point(x[k],y[k])
                                   , point(x[i],y[i]))||
                 point_in_triangle(point(0,0),point(x[k],y[k]), point(x[i],y[i])
                                   , point(x[j],y[j]))||
                 point_in_triangle(point(0,0),point(x[k],y[k]), point(x[j],y[j])
                                   , point(x[i],y[i])))
                ans++;
            }

        return ans;
    }
};