点在多边形内部

点在多边形内部

射线法，从判断点向上做一条射线，当与多边形交点个数为奇数个时，则点在多边形内部。

边界条件(点在顶点上，点在边上，通过叉积等于0与点积小于等于0来判断）

边界条件，凸顶点判断一次，凹顶点判断两次

边界条件，当连线与边重叠时，不进行判断，点一定在多边形外部。

((c.x >= a.x && c.x < b.x) || (c.x >= b.x && c.x < a.x))

#include<bits/stdc++.h>
using namespace std;
using LL = long long;

struct Point {
public:
    int x, y;

    Point(int _x, int _y) : x(_x), y(_y) {}

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

int dot(const Point& a, const Point& b) {
    return a.x * b.x + a.y * b.y;
}

int cross(const Point& a, const Point& b) {
    return a.x * b.y - b.x * a.y;
}

vector<Point> arr;
bool in(Point c) {
    int n = arr.size();
    int ans = 0;
    for (int i = 0, j = n - 1; i < n; j = i++) {
        Point a = arr[j], b = arr[i];
        if (dot(c - a, c - b) <= 0 && cross(c - a, c - b) == 0) return 0;
        if (((c.x >= a.x && c.x < b.x) || (c.x >= b.x && c.x < a.x)) && c.y < a.y + 1.0 * (b.y - a.y) / (b.x - a.x) * (c.x - a.x)) {
            ans = !ans;
        }
    }
    return ans;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    #ifndef ONLINE_JUDGE
        freopen("input.txt", "r", stdin);
        freopen("output.txt", "w", stdout);
    #endif
    int n, q, x, y;
    cin >> n;
    for (int i = 0; i < n; ++i) {
        cin >> x >> y;
        arr.push_back({x, y});
    } 
    cin >> q;
    int ans = 0;
    for (int i = 0; i < q; ++i) {
        cin >> x >> y;
        if (in({x, y})) ++ans;
    }
    cout << ans << endl;
    return 0;
}