几何模板

点/向量定义

struct vec{ // 向量
    T x, y;
    vec(){}
    vec(T dx, T dy){x = dx, y = dy;}
    vec(vec from, vec to){x = to.x - from.x, y = to.y - from.y;}
    vec operator +(const vec oth)const {return {x + oth.x, y + oth.y};}
    vec operator -(const vec oth)const {return {x - oth.x, y - oth.y};}
    vec operator *(double times)const {return {x * times, y * times};}
    T operator *(const vec oth){return x*oth.y - y*oth.x;} // 外积(叉积)
    T operator ^(const vec oth){return x*oth.x + y*oth.y;} // 内积(点积)
    T len()const {return std::sqrt(x * x + y * y);}
    bool operator <(const vec & oth)const{
        if(y == oth.y) return x < oth.x;
        return y < oth.y;
    }
};
typedef vec point; // 点

两线段相交

三角形外心

由于涉及到平方的计算，因此要考虑使用double或__int128_t

static pair<double, double> circumcentre_pr(point p0, point p1, point p2){ // 求三角形外心
    T a = 2 * (p1.x - p0.x), b = 2 * (p1.y - p0.y);
    T c = 2 * (p2.x - p0.x), d = 2 * (p2.y - p0.y);
    T b1 = p1.x * p1.x - p0.x * p0.x + p1.y * p1.y - p0.y * p0.y;
    T b2 = p2.x * p2.x - p0.x * p0.x + p2.y * p2.y - p0.y * p0.y;
    double dem = a * d - b * c;
    T d1 = b1 * d - b2 * b, d2 = a * b2 - c * b1;
    return {1.0 * d1 / dem, 1.0 * d2 / dem};
}

static point circumcentre(point p0, point p1, point p2){ // 求三角形外心
    pair<double, double> ans = circumcentre_pr(p0, p1, p2);
    return point((T)ans.first, (T)ans.second);
}

当然，还有另一种计算方法，其优势在于可以预处理部分参数，避免重复计算

坐标系旋转

在将坐标系逆时针旋转$\theta$角后，原坐标与新坐标的关系如下

$$\left(\begin{array}{l}x^{\prime} \\y^{\prime}\end{array}\right)=\left(\begin{array}{cc}\cos \theta & -\sin \theta \\\sin \theta & \cos \theta\end{array}\right)\left(\begin{array}{l}x \\y\end{array}\right)\\\begin{aligned}x'&=x\cos\theta+y\sin\theta\\y'&=y\cos\theta-x\sin\theta\end{aligned}$$

(不)完整代码

写到心力憔悴，晚点再来完善

PS: POJ上就别用这套模板了，得该成C98的风格（心累）

template<class T>
struct geometry{

    const constexpr static double eps = 1e-8;

    struct vec{ // 向量
        T x, y;
        vec(){}
        vec(T dx, T dy){x = dx, y = dy;}
        vec(vec from, vec to){x = to.x - from.x, y = to.y - from.y;}
        vec operator +(const vec oth)const {return {x + oth.x, y + oth.y};}
        vec operator -(const vec oth)const {return {x - oth.x, y - oth.y};}
        vec operator *(double times)const {return {x * times, y * times};}
        T operator *(const vec oth){return x*oth.y - y*oth.x;} // 外积(叉积)
        T operator ^(const vec oth){return x*oth.x + y*oth.y;} // 内积(点积)
        T len()const {return (T)std::sqrt(x * x + y * y);}
        bool operator <(const vec & oth)const{
            if(y == oth.y) return x < oth.x;
            return y < oth.y;
        }
    };
    typedef vec point; // 点
    struct edge{ // 线段
        point a, b;
    };

    static T sign_test(T val){
        if(val > eps) return 1;
        if(val < -eps) return -1;
        return 0;
    }

    static T dist(point p1, point p2){
        return vec(p1, p2).len();
    }

    static bool on_edge(point p, edge e){ // 判断点是否在线段(含端点)上
        return sign_test((e.a-p)*(e.b-p)) == 0 && sign_test((e.a-p)^(e.b-p)) <= 0;
    }

    static bool is_cross(edge l1, edge l2){ // 规范相交(不存在三点共线)
        T s1 = sign_test((l1.b-l1.a)*(l2.a-l1.a)), s2 = sign_test((l1.b-l1.a)*(l2.b-l1.a));
        T s3 = sign_test((l2.b-l2.a)*(l1.a-l2.a)), s4 = sign_test((l2.b-l2.a)*(l1.b-l2.a));
        if(s1 * s2 < 0 && s3 * s4 < 0) return true;
        return false;
    }

    static point cross_point(edge l1, edge l2){
        double area1 = fabs(vec(l1.a, l2.a) * vec(l1.a, l2.b));
        double area2 = fabs(vec(l1.b, l2.a) * vec(l1.b, l2.b));
        return (l1.a * area1 + l1.b * area2) * (1 / (area1 + area2));
    }

    static double sine(vec v1, vec v2){return (v1 * v2) * 1.0 / (v1.len() * v2.len());}
    static double cosine(vec v1, vec v2){return (v1 ^ v2) * 1.0 / (v1.len() * v2.len());}

    static T triangle_area(vec v1, vec v2){
        T result = (v1 * v2) / 2;
        return result>0?result:-result;
    }

    static pair<double, double> circumcentre_pr(point p0, point p1, point p2){ // 求三角形外心
        T a = 2 * (p1.x - p0.x), b = 2 * (p1.y - p0.y);
        T c = 2 * (p2.x - p0.x), d = 2 * (p2.y - p0.y);
        T b1 = p1.x * p1.x - p0.x * p0.x + p1.y * p1.y - p0.y * p0.y;
        T b2 = p2.x * p2.x - p0.x * p0.x + p2.y * p2.y - p0.y * p0.y;
        double dem = a * d - b * c;
        T d1 = b1 * d - b2 * b, d2 = a * b2 - c * b1;
        return {1.0 * d1 / dem, 1.0 * d2 / dem};
    }

    static point circumcentre(point p0, point p1, point p2){ // 求三角形外心
        pair<double, double> ans = circumcentre_pr(p0, p1, p2);
        return point((T)ans.first, (T)ans.second);
    }

    static void sort_by_angle(vector<point> & pts){
        for(int i=1; i<pts.size(); i++)
            if(pts[i] < pts[0]) swap(pts[i], pts[0]);
        point base = pts[0];
        sort(pts.begin()+1, pts.end(), [&](point x1, point x2){
            vec v1(base, x1), v2(base, x2);
            double k = v1 * v2;
            return k==0?v1.len()<v2.len():k>0; // 按辐角排序，相同则短者优先
        });
    }

    static vector<point> convec_hull(vector<point> & pts){
        sort_by_angle(pts);
        int steck[pts.size()], head=0;
        steck[head++] = 0;
        for(int i=1; i<pts.size(); i++){
            while(head > 1 && vec(pts[steck[head-2]], pts[steck[head-1]])*vec(pts[steck[head-1]], pts[i])<=0) head--;
            steck[head++] = i;
        }
        vector<point> ret(head);
        for(int i=0; i<head; i++) ret[i] = pts[steck[i]];
        return ret;
    }
};

using geo = geometry<double>;