Created
December 12, 2014 15:18
-
-
Save ik11235/361a92bf6f44551dfb4c to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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