Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
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;
}
};
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment