0012:A Point in a Triangle

点が三角形の内部にあるかを判定する。

解答中の関数
dot()→内積
cross()→外積
is_point_on_line()→点が線分の上にあるか。
is_intersected_ls()→線分の交差判定。
inside()→点が多角形の内部にあるか。

関数 inside(point p, vector ps)
点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;
}