板子测试
边界情况：
点在多边形上，特判
交点为多边形顶点，将该点视作在射线的上侧。
复杂度 $O(n)$
这种方法不会有精度问题。
如果是凸多边形，可以用$n$次 $to—left$ 测试 有$O(n log n)$ 方法

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define endl '\n'
#define rep(i, l, r) for (auto(i) = (l); (i) <= (r); ++(i))
const int N = 5e3+10;
struct Point{
    ll x, y;
}a[N];
Point operator - (Point a, Point b){
    return {a.x - b.x, a.y - b.y};
}
ll operator * (Point a, Point b){
    return a.x*b.x + a.y*b.y;
}
ll operator ^ (Point a, Point b){
    return a.x*b.y - a.y*b.x;
}
// to-left测试 判断点在直线的哪一边
int toleft(Point a, Point b, Point c){
    ll temp = (b-a) ^ (c-a);
    if(temp > 0) return 1; // 在左边
    else if(temp == 0) return 0; //在线上
    else return -1; //在右边
}
// 判断点c是不是在 线段ab 上
bool cont(Point a, Point b, Point c){
    ll temp = (b-a) ^ (c-a);
    //这种判断方式并不好 因为如果x相同要考虑y坐标
    //所以一般用点积小于等于0来判断
    //if(!temp&&max(a.x,b.x)>=c.x&&min(a.x,b.x)<=c.x) return true;
    return !temp && ((c-a) * (c-b) <= 0);
    //return false;
}
void Solve(){
    int n;
    cin >> n;
    rep(i, 0, n-1) cin >> a[i].x >> a[i].y;
    int m;
    cin >> m;
    rep(i, 1, m){
        Point c;
        cin >> c.x >> c.y;
        Point d = c;
        d.x ++;
        int res = 0;
        // 回转数 判断点是否在多边形内
        rep(j, 0, n-1){
            if(cont(a[j],a[(j+1)%n],c)){
                cout << "EDGE" << endl;
                break;
            }
            int t1 = toleft(c, d, a[j]);
            int t2 = toleft(c, d, a[(j+1)%n]);
            int t3 = toleft(a[j], a[(j+1)%n], c);
            if(t1 >= 0 && t2 < 0 && t3 < 0) res --;
            else if(t1 < 0 && t2 >= 0 && t3 > 0) res ++;
            if(j == n-1) cout << res << endl;
        }
    }
    return;
}
int main(){
    std::ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    Solve();
    return 0;
} 

两直线相交

struct Point{
    double x, y;
}a[N];
Point operator - (Point a, Point b){
    return {a.x - b.x, a.y - b.y};
}
Point operator + (Point a, Point b){
    return {a.x + b.x, a.y + b.y};
}
double operator * (Point a, Point b){
    return a.x*b.x + a.y*b.y;
}
double operator ^ (Point a, Point b){
    return a.x*b.y - a.y*b.x;
}
Point operator * (double b,Point a){
    return {a.x * b, a.y * b};
}
int toleft (Point a, Point b, Point c){
    ll temp = (b-a) ^ (c-a);
    if(temp == 0) return 0;
    else if(temp > 0) return 1;
    else return -1;
}
//如果是线段和直线的交点，先用这个判断有没有交点，避免精度误差。
bool inleft (Point a, Point b, Point c, Point d){
    ll t1 = toleft(a, b, c);
    ll t2 = toleft(a, b, d);
    if(t1 <= 0 && t2 >= 0) return true;
    if(t1 >= 0 && t2 <= 0) return true;
    return false;
}
//直线AB和直线CD的交点
Point corsspoint(Point a, Point b, Point c, Point d){
    Point v1 = b - a;
    Point v2 = d - c;
    double t1 = v2 ^ (a - c);
    double t2 = v1 ^ v2;
    return a + ((t1/t2) * v1);
}

极角序