凸包

//扱える値は int 値のみ
//0,1,2 という３点を与えたとき結果は 0 -> 1 -> 2 -> 0 になる。
//結果の点の数は最初に戻るので１つ増えることに注意。

struct Point{
  int x, y;
  Point(){};
  Point(int x, int y):x(x), y(y){};
  bool operator <(const Point &p) const {
    return x < p.x || (x == p.x && y < p.y);
  }
  bool operator ==(const Point &p) const {
    return (x == p.x && y == p.y);
  }
};

long long cross(const Point &O, const Point &A, const Point &B){
  return (long long)(A.x - O.x) * (B.y - O.y) - (long long)(A.y - O.y) * (B.x - O.x);
}

vector<Point> convex_hull(vector<Point> P){
  int chn = P.size();
  int chk = 0;
  vector<Point> H(2*chn);

  sort(P.begin(), P.end());

  for(int i = 0; i < chn; i++){
    while(chk >= 2 && cross(H[chk-2], H[chk-1], P[i]) <= 0)chk--;
    H[chk++] = P[i];
  }

  for(int i = chn-2, t = chk+1; i >= 0; i--){
    while(chk >= t && cross(H[chk-2], H[chk-1], P[i]) <= 0)chk--;
    H[chk++] = P[i];
  }

  H.resize(chk);
  return H;
}


//凸包を用いた点０と三角１２３の内外判定
//線上は内部とみなす 角上は外部とみなす
//x2 == x3 として 点０が線分１２上かも判定できる
int isIn(int x0, int y0, int x1, int y1, int x2, int y2, int x3, int y3){
  vector<Point> vp;

  vp.pb(Point(x0, y0));
  vp.pb(Point(x1, y1));
  vp.pb(Point(x2, y2));
  vp.pb(Point(x3, y3));

  vector<Point> vp1 = convex_hull(vp);

  if(count(all(vp1), Point(x0, y0)) == 0){
    return 1;
  }
  return 0;
}