0012:A Point in a Triangle
点が三角形の内部にあるかを判定する。
解答中の関数
dot()→内積
cross()→外積
is_point_on_line()→点が線分の上にあるか。
is_intersected_ls()→線分の交差判定。
inside()→点が多角形の内部にあるか。
関数 inside(point p, vector
点pが多角形psの内部にあるか判定。
方法
点pから正の方向にx軸に平行な半直線を伸ばす。
半直線と多角形の辺が交差した回数が
奇数なら内部、偶数なら外部にある。
#include<cmath> #include<algorithm> #include<iostream> #include<vector> #include<climits> #include<cfloat> using namespace std; double EPS = 1e-10; double add(double a, double b){ if(abs(a+b) < EPS * (abs(a)+abs(b)))return 0; return a+b; } struct point{ double x, y; point(){} point(double x,double y) : x(x) , y(y){} point operator + (point p){ return point(add(x,p.x), add(y,p.y)); } point operator - (point p){ return point(add(x,-p.x), add(y,-p.y)); } point operator * (double d){ return point(x*d,y*d); } }; double dot(point a, point b) { return (a.x * b.x + a.y * b.y); } double cross(point a, point b) { return (a.x * b.y - a.y * b.x); } int is_point_on_line(point a, point b, point c) { return cross(b-a, c-a)==0.0 && (dot(b-a, c-a) > -EPS) && (dot(a-b, c-b) > -EPS); } int is_intersected_ls(point a1, point a2, point b1, point b2) { if(cross(a1-a2,b1-b2)==0){ return is_point_on_line(a1,a2,b1) || is_point_on_line(a1,a2,b2) || is_point_on_line(b1,b2,a1) || is_point_on_line(b1,b2,a2); } else { return ( cross(a2-a1, b1-a1) * cross(a2-a1, b2-a1) < EPS ) && ( cross(b2-b1, a1-b1) * cross(b2-b1, a2-b1) < EPS ); } } int inside(point p, vector<point> ps){ point a,b; a=b=p; b.x=1000000; int n=ps.size(); ps.push_back(ps[0]); double ymx=-DBL_MAX,ymn=DBL_MAX; for(int i=0;i<n;i++){ ymx=max(ymx,ps[i].y); ymn=min(ymn,ps[i].y); } if(a.y<=ymn||a.y>=ymx)return 0; for(int i=0;i<n;i++){ if(is_point_on_line(ps[i],ps[i+1],p))return 0; } int cnt1=0; for(int i=0;i<n;i++) if(is_point_on_line(a,b,ps[i]))cnt1++; int cnt=0; for(int i=0;i<n;i++) if(is_intersected_ls(ps[i],ps[i+1],a,b))cnt++; return (cnt-cnt1)%2; } int main(void){ point in[4],p; vector<point>ps; while(cin>>in[1].x>>in[1].y>>in[2].x>>in[2].y>>in[3].x>>in[3].y>>p.x>>p.y){ ps.clear(); for(int i=1;i<4;i++) ps.push_back(in[i]); if(inside(p,ps))cout << "YES" << endl; else cout << "NO" << endl; } return 0; }