在计算几何中,判断点是否内包于多边形之中,就是点的内包问题。

解决的思路就是,对于给定点p,作一条沿x轴正方向的射线,然后计算这条射线与多边形的边相交的次数。

首先判断点p是否在边上,如果在边上的话就直接return

如果相交的次数是奇数,那么它就是内包的。否则,点处于多边形的外部。

具体求相交次数的方法就是

遍历多边形上相邻的两点gi gi+1 ,设向量a = gi – p, b = gi+1– p

如果a的y坐标大于b的y坐标,那么就交换a、b

这时,如果a、b的外积为正,且a、b的y坐标一负一正,那么射线与线段gigi+1相交。

题目:CGL_3_C

AC代码:

#include <bits/stdc++.h>
using namespace std;
#define MAXN 105

const double EPS = (1E-8);

class Point
{
public:
    double x, y;
    Point()
    {
    }
    Point(double x, double y)
    {
        (*this).x = x;
        (*this).y = y;
    }

    double operator^(const Point &p) const //叉乘
    {
        return x * p.y - y * p.x;
    }

    double operator*(const Point &p) const //点乘
    {
        return x * p.x + y * p.y;
    }

    Point operator*(const double &d) const
    {
        return Point(x * d, y * d);
    }

    Point operator/(const double &d) const
    {
        return Point(x / d, y / d);
    }

    Point operator-(const Point &p) const
    {
        return Point(x - p.x, y - p.y);
    }

    Point operator+(const Point &p) const
    {
        return Point(x + p.x, y + p.y);
    }

    double sqr()
    {
        return x * x + y * y;
    }
    double abs()
    {
        return sqrt(sqr());
    }

    double distance(const Point &p)
    {
        return fabs((*this - p).abs());
    }

    void print()
    {

        printf("%.10lf %.10lf\n", x, y);
    }

    void read()
    {
        cin >> x >> y;
    }
};

class Line
{
public:
    Point p1, p2;
    Line();
    Line(Point p1, Point p2)
    {
        (*this).p1 = p1;
        (*this).p2 = p2;
    }
};

Point pp[MAXN];
int n;
int contains(Point p) //内包-》2,在边上-》1,在外部-》0
{
    int js=0;
    for (int i = 0; i < n; ++i)
    {
        Point a = pp[i] - p;
        Point b = pp[(i + 1) % n] - p;

        if (fabs((a ^ b)) < EPS && a * b < EPS)
            return 1; //在边上

        if (a.y > b.y)
            swap(a, b);

        if ((a ^ b) > EPS && a.y < EPS && b.y > EPS)
            js++;
    }

    return (js%2?2:0);
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> n;
    for (int i = 0; i < n; ++i)
    {
        pp[i].read();
    }

    int q;
    cin >> q;

    Point tmp;
    while (q--)
    {
        tmp.read();
        cout<<contains(tmp)<<endl;
    }
}

转载请注明来源:https://www.longjin666.top/?p=815

欢迎关注我的公众号“灯珑”,让我们一起了解更多的事物~

你也可能喜欢

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注