点在多边形内

点的定义

struct P {
    double x, y;
    double dot(const P &p) const { return x * p.x + y * p.y; }
    double det(const P &p) const { return x * p.y - y * p.x; }
};

其中 dot 是点积，det 是叉积

与 $0$ 的关系

const double EPS = 1e-7;
int sign(const double &a) {
    return a < -EPS ? -1 : a > EPS;
}

如果 $a < 0$，返回 $-1$

如果 $a=0$，返回 $0$

如果 $a>0$，返回 $1$

判断点在线段上

bool inSeg(P u, P v, P p) {
    return sign((u - p).det(v - p)) == 0 && sign((u - p).dot(v - p)) <= 0;
}

如果点 $p$ 在线段 $\overline{uv}$ 上，那么首先需要保证在直线 $\overline{uv}$ 上，也就是 $\vec{pu} \times \vec{pv}=0$

其次要保证 $p$ 落在线段 $\overline{uv}$ 上，也就是 $\vec{pu} \cdot \vec{pv} \le 0$

判断点在多边形内

int check_in_pol(vector<P> poly, P p) {
    int ret = 0, k = poly.size();
    for(int i = 0 ; i < k ; ++ i) {
        P u = poly[i], v = poly[(i + 1) % k];
        if (inSeg(u, v, p)) return 1;
        if (sign(u.y - v.y) <= 0) swap(u, v);
        if (sign(p.y - u.y) > 0 || sign(p.y - v.y) <= 0) continue;
        ret += sign((v - p).det(u - p)) > 0;
    }
    return ret & 1;
}

传入的 vector<P> poly 应保证是按照顺时针给出的

首先如果在某条线段上的话，直接返回 true 即可

否则就判断 $p$ 是否在线段 $\overline{uv}$ 左侧（也就是从 $u$ 往右侧引出一条射线）

对于一条线段 $\overline{uv}$，把它拆成除掉 $v$ 的线段即可