计算几何代码模板

这里记录了计算几何方面平时个人常用的代码模板。

计算几何

//#pragma comment(linker, "/STACK:102400000,102400000")
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
//#define int ll
typedef pair<int,int>pii;
#define ff first
#define ss second
#define debug(x) std:: cerr << #x << " = " << x << std::endl;
const int maxn=2e5+10,inf=0x3f3f3f3f,mod=1000000007;
const ll INF=0x3f3f3f3f3f3f3f3f;
const int MAXN = 100000;
const double EPS = 1e-8;
inline bool dcmp(double x, double y = 0)
{// 带误差比较
    return fabs(x - y) <= EPS;
}
typedef struct Vec
{
    /*
     * 向量（Vector）或点
     * 使用原点到一个点 (x, y) 的有向线段表示向量
     * 从点 A 到点 B 的向量表示为 A - B
     */
    double x, y;
    Vec(double x = 0, double y = 0) : x(x), y(y) {}
    // 相加
    Vec operator+(const Vec &v) const
    {
        return Vec(x + v.x, y + v.y);
    }
    // 相减
    Vec operator-(const Vec &v) const
    {
        return Vec(x - v.x, y - v.y);
    }
    // 数乘（伸长、缩短）
    Vec operator*(double d) const
    {
        return Vec(x * d, y * d);
    }
    Vec operator/(const double d) const
    {
        return Vec(x / d, y / d);
    }
    // 范数，用来比较长度，等于长度的平方
    double norm() const
    {
        return x * x + y * y;
    }
} Pt;
// 点乘
double dot(const Vec &a, const Vec &b)
{
    return a.x * b.x + a.y * b.y;
}
// 叉乘
double cross(const Vec &a, const Vec &b)
{
    return a.x * b.y - a.y * b.x;
}
struct Seg
{// 线段（Segment），用两个点表示
    Pt a, b;
    Seg(const Pt &a, const Pt &b) : a(a), b(b) {}
    bool include(const Pt &p)
    {//线段包含点（点在线段上）,若卡精度使用dis
        // PA × PB = 0：PA 与 PB 共线，即点在线段所在的直线上
        // PA · PB = 0：PA 与 PB 方向不同（A 和 B 分别在 P 的两边），如果 PA · PB = 0 则 P = A 或 P = B
        return dcmp(cross(a - p, b - p)) && dot(a - p, b - p) <= 0;
    }
    double get_distance(Pt p, Pt A, Pt B)
    {
        Pt Ap, Ab, Bp;
        Ap.x = p.x - A.x, Ap.y = p.y - A.y;
        Ab.x = B.x - A.x, Ab.y = B.y - A.y;
        Bp.x = p.x - B.x, Bp.y = p.y - B.y;
        double r = (Ap.x*Ab.x + Ap.y*Ab.y)*1.0 / (Ab.x*Ab.x + Ab.y*Ab.y);
        if (r <= 0)return sqrt(Ap.x*Ap.x*1.0 + Ap.y*Ap.y);
        if (r >= 1)return sqrt(Bp.x*Bp.x*1.0+Bp.y*Bp.y);
        double px = A.x + Ab.x*r;
        double py = A.y + Ab.y*r;
        return sqrt((p.x-px)*(p.x-px)+(p.y-py)*(p.y-py));
    }
    double dis(const Pt &p)
    {//点到线段距离,可用来判断点是否在线段上
        return get_distance(p,a,b);
    }
};
struct Line
{// 直线，用两个点表示
    Pt a, b;
    Line() {} // 提供一个不需要参数的构造函数
    Line(const Pt &a, const Pt &b) : a(a), b(b) {}
    bool include(const Pt &p) const
    {
        return dcmp(cross(a - p, b - p));
    }
    // 两直线关系（交点个数）
    // 0 表示平行（无交点）
    // 1 表示相交（一个交点）
    // -1 表示重合（无数个交点）
    int relation(const Line &y)
    {
        if (include(y.a) && include(y.b)) return -1;
        else if (dcmp(cross(b - a, y.b - y.a))) return 0;
        else return 1;
    }
    // 求两直线交点（需要保证两直线有交点）
    Pt intersect(const Line &y)
    {
        double s1 = cross(y.a - a, y.b - a), s2 = cross(y.b - b, y.a - b);
        return a + (b - a) * s1 / (s1 + s2);
    }
};
// 求凸包用的点
int n;
Pt a[MAXN + 1];
// 凸包极角排序的比较函数
inline bool compare(const Pt &a, const Pt &b)
{
    // 两个向量
    Vec va = a - ::a[1], vb = b - ::a[1];
    double t = cross(va, vb);
    if (!dcmp(t)) return t > 0; // OA -> OB 是逆时针，则 A 极角序在先
    else return va.norm() < vb.norm(); // norm 较小的长度较小
}
struct Poly
{
    std::vector<Pt> pts;
    bool include(const Pt &p) const
    {
        int cnt = 0;
        // 判断与每条边有没有交点
        for (size_t i = 0; i < pts.size(); i++)
        {
            // 枚举相邻的每两个点
            const Pt &a = pts[i], &b = pts[(i + 1) % pts.size()];
            // 如果点 P 在边 AB 上
            if (Seg(a, b).include(p)) return true;
            // 详见图
            double d1 = a.y - p.y, d2 = b.y - p.y, tmp = cross(a - p, b - p);
            if ((tmp >= 0 && d1 >= 0 && d2 < 0) || (tmp <= 0 && d1 < 0 && d2 >= 0)) cnt++;
        }
        // 奇数的交点
        return cnt % 2 == 1;
    }
    // 多边形面积（有向面积）
    double area() const
    {
        double res = 0;
        for (size_t i = 0; i < pts.size(); i++)
        {
            // 枚举每两个点
            const Pt &a = pts[i], &b = pts[(i + 1) % pts.size()];
            res += cross(a, b);
        }
        return res / 2;
    }
    // 求凸包（Convex），结果储存在自身 pts 中
    void convex()
    {
        // 找出最左下角的点
        int id = 1;
        for (int i = 1; i <= n; i++)
        {
            if (a[i].x < a[id].x || (a[i].x == a[id].x && a[i].y < a[id].y)) id = i;
        }
        if (id != 1) std::swap(a[1], a[id]);
        // 排序
        std::sort(a + 2, a + n + 1, &compare);
        // 极角序扫描
        pts.push_back(a[1]);
        for (int i = 2; i <= n; i++)
        {
            // 比较，如果最后一个点需要被删掉则弹出（pop_back）
            while (pts.size() >= 2 && cross(a[i] - pts[pts.size() - 2], pts.back() - pts[pts.size() - 2]) >= 0) pts.pop_back();
            pts.push_back(a[i]);
        }
    }
};
signed main(signed argc, char const *argv[])
{
    std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    #ifdef DEBUG
        freopen("input.in", "r", stdin);
    //	freopen("output.out", "w", stdout);
    #endif

    return 0;
}
/*
 * 2021-04-14-20.08.32
*/