面试中几乎不考。

射线法

射线法，由基准点水平向右生成射线Y，如果Y与多边形的交点数为偶数，则在外部，为奇数则在图内部，特殊情景另外考虑

hdu1756-射线法模板：

        struct Point {
            double x, y;
            Point(double x=0,double y=0):x(x),y(y){}
            //向量+
            Point operator +(const Point& b) const {
                return Point(x + b.x, y + b.y);
            }
            //向量-
            Point operator -(const Point& b)const {
                return Point(x - b.x, y - b.y);
            }
            //点积
            double operator *(const Point& b)const {
                return x*b.x + y*b.y;
            }
            //叉积
            //P^Q>0，P在Q的顺时针方向；<0，P在Q的逆时针方向；=0，P，Q共线，可能正向可能反向
            double operator ^(const Point& b)const {
                return x*b.y - b.x*y;
            }
        };
        float eps = 1e-6;
        int dcmp(double x) {
            if (fabs(x) < eps)
                return 0;
            else
                return x < 0 ? -1 : 1;
        }
        bool OnSegment(Point& P1, Point& P2,Point& Q) {//判断点Q是否在P1和P2的线段上
            return dcmp((P1 - Q) ^ (P2 - Q)) == 0 && dcmp((P1 - Q) * (P2 - Q)) <= 0;//前一个判断点Q在P1P2直线上 后一个判断在P1P2范围上
        }
        bool InPolygon(Point& P,vector<Point>& v) {//射线法
            bool flag = false;
            Point P1, P2;
            int n = v.size();
            for (int i = 0, j = n - 1; i < n; j = i++) {
                P1 = v[i];
                P2 = v[j];
                if (OnSegment(P1, P2, P)) 
                    return true;
                //前一个判断min(P1.y,P2.y)<P.y<=max(P1.y,P2.y)
                //后一个判断被测点 在 射线与边交点 的左边
                if ((dcmp(P1.y - P.y) > 0 != dcmp(P2.y - P.y) > 0) && dcmp(P.x - (P.y - P1.y)*(P1.x - P2.x) / (P1.y - P2.y) - P1.x) < 0)
                    flag = !flag;
            }
            return flag;
        }