二维计算几何模板

前提条件

#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;
typedef double temType; // 需要用到的类型

点（向量）

已知

$(x,y)$，点坐标或向量坐标

函数

相加、相减、与常数相加、点乘、叉乘、旋转、标准化

向量旋转

$$
\begin{bmatrix} \cos \theta & -\sin \theta \ \sin \theta & \cos \theta \end{bmatrix}
\begin{bmatrix} x \ y \end{bmatrix} =
\begin{bmatrix} x\cos\theta-y\sin\theta \ x\sin\theta+y\cos\theta \end{bmatrix}
$$

代码

// 点或向量
struct point{
    temType x, y;
    point(): x(0), y(0){}
    point(temType _x, temType _y): x(_x), y(_y){}
    point(const point &t){x = t.x;y = t.y;};
    point operator-(const point& t) const{return {x-t.x, y-t.y};}   // 相减
    point operator+(const point& t) const{return {t.x+x, t.y+y};}   // 相加
    point operator*(temType t) const{return {x*t, y*t};}            // 与常数相乘
    temType cdot(const point& t) const{return t.x*x+t.y*y;}                // 点乘
    temType times(const point& t) const{return x*t.y-y*t.x;}               // 叉乘
    bool operator==(const point& t) const{return x==t.x && y==t.y;}
    bool operator!=(const point& t) const{return x!=t.x || y!=t.y;}
    temType length() const{return sqrt(x*x+y*y); }
    void normalize() {                                                  //标准化
        temType sqt = sqrt(x*x+y*y);
        x = x/sqt; y = y/sqt;
    }
    point rotation(temType t) const{                                    //向量旋转
        temType cost=cos(t), sint=sin(t);
        return {x*cost-y*sint, x*sint+y*cost};
    }
};
typedef struct point pit;
typedef struct point vtr;

极坐标点

struct polar{
    temType p, e;
    polar(temType _p, temType _e): p(_p), e(_e){}
};
typedef struct polar plr;

polar toPolar(const pit& t){ return {sqrt(t.x*t.x+t.y*t.y),atan2(t.y,t.x)}; }
pit toRect(const plr& t){ return {t.p*cos(t.e), t.p*sin(t.e)}; }

线段

已知

已知线段两端端点$A,B$

函数

跨立实验，快速排斥实验

代码

// 线段
struct segment{
    pit A, B;
    segment(const pit& _A, const pit& _B): A(_A), B(_B){}
    pit midpoint() const{return {(A.x+B.x)/2.0, (A.y,B.y)/2.0};} // 中点
    bool rapidRejectionExp(const segment& t) const { // 快速排斥实验 TODO 这里有一些错误
        pit minTmp(min(A.x, B.x), min(A.y, B.y));
        pit maxTmp(max(A.x, B.x), max(A.y, B.y));
        return  (t.A.x >= minTmp.x && t.A.x <= maxTmp.x) && (t.A.y >= minTmp.y && t.A.y <= maxTmp.y) ||
                (t.B.x >= minTmp.x && t.B.x <= maxTmp.x) && (t.B.y >= minTmp.y && t.B.y <= maxTmp.y);
    }
    bool straddleExp(const segment& t) const{ // 跨立实验
//        if(!rapidRejectionExp(t)) return false;
        vtr AB = B-A, tba = t.A-t.B;
        temType t1 = AB.times(t.A-A) * AB.times(t.B-A), t2 = tba.times(A-t.B)*tba.times(B-t.B);
        if(t1 < 0 && t2 < 0) return true;
        else return false;
    }
};
typedef struct segment seg;

直线与射线

已知

已知直线上一点和向量，$P,\vec{s}$

函数

获得直线上的一点

求两直线交点

公式
$$
P=A-\frac{\vec{b}\cdot\vec{BA}}{\vec{b}\cdot\vec{a}}\cdot\vec{a}
$$

代码

struct line{
    pit P;
    vtr s;
    line(const pit& _P, const vtr& _s): P(_P), s(_s) {s.normalize();}
    pit getPoint(temType t) const {return P + s*t;}
    bool ispParallel(const line& t) const{return s.times(t.s)==0;} // 平行
    bool isCoincide(const line& t) const{return s.times(t.s)==0 && ((s.times(P-t.P)==0));} // 重合
    pit intersection(const line& t) const{ return P - s * (t.s.times(P-t.P) / t.s.times(s)); }
};
typedef struct line line; // 直线
typedef struct line ray; // 射线

圆

已知

圆心$O$，半径$r$

代码

struct circle{
    pit O;
    temType r;
    circle(const pit& _O, temType _r): O(_O), r(_r){}
};
typedef struct circle cle;

直线与圆

已知

直线：$P$点坐标$(P_x,P_y)$，$\vec{s}=(s_x,s_y)$

圆：$O$点坐标$(O_x,O_y)$，圆的半径$r$

推导

$$
|OE|= \frac{\vec{s} \times \vec{PO}}{|\vec{s}|} \
|PE|= \frac{\vec{s} \cdot \vec{PO}}{|\vec{s}|}\
|AE|=|BE|=\sqrt{r^2-|OE|^2}\
|PA|=|PE|-|AE|\
|PB|=|PE|+|BE|\
A=P+\frac{|PA|}{|\vec{s}|}\cdot\vec{s}\
B=P+\frac{|PB|}{|\vec{s}|}\cdot\vec{s}
$$

代码

seg intersectionOfLineAndCircle(const line& p, const cle& c){
    vtr PO = c.O - p.P;
    temType OE = p.s.times(PO), PE = p.s.times(PO);
    temType tmp = sqrt(c.r*c.r-OE*OE);
    return {p.getPoint(PE-tmp), p.getPoint(PE+tmp)};
}

凸包

已知

已知一个二维坐标图中每个顶点，求最小周长能够包含所有所有顶点的凸包

思路

先将点双关键字排序，横坐标为第一关键字，纵坐标为第二关键字

排序之后

图片向量方向迭代方向

之后维护单调单调栈，其中栈顶为$S_1$，栈顶第二元素为$S_2$，当前检查的点为$P$，由于凸包是不会出现右转的，所以当出现$\vec{S_2S_1}\times\vec{S_1P}<0$说明栈顶的元素不是最优凸包，弹出栈顶重复上一步。

第一次循环迭代之后，会发现求完了下凸包先在需要倒转迭代方向，再次遍历

第二次迭代完善上凸包，最终会形成一个最短周长的能够包含所有顶点的凸包

注意：运行结果最后还会添加一次初始节点，那么周长就为$$\sum_{i=0}^{tp-1}|\vec{p_ip_{i+1}}|$$

代码

const int N = 1e5+10;
pit p[N];
int stk[N<<1];
int tp;

bool cmp(pit &a, pit &b){
    if(a.x == b.x) return a.y < b.y;
    return a.x < b.x;
}

int main() {
    debug;
    int n;
    temType xt, yt;
    cin >> n;
    for(int i = 0; i < n; ++i) {
        cin >> xt >> yt;
        p[i] = point(xt, yt);
    }
    sort(p, p+n, cmp);
    stk[++tp] = 0;
    for(int i = 1; i < n; ++i) {
        while (tp >= 2 && ((p[stk[tp]]-p[stk[tp-1]]).times(p[i]-p[stk[tp]]) < 0)) tp--;
        stk[++tp] = i;
    }
    int tmp = tp;
    for(int i = n-1; i >= 0; --i){
        while (tp > tmp && ((p[stk[tp]]-p[stk[tp-1]]).times(p[i]-p[stk[tp]]) < 0)) tp--;
        stk[++tp] = i;
    }
    temType ans = 0;
    for(int i = 1; i <= tp; ++i) {
        ans += (p[stk[i]] - p[stk[i-1]]).length();
    }
    printf("%.2f", ans);
}