计算几何

板子

---

基础函数

const double eps = 1e-8;
struct Point {
    double x, y;
    Point() {}
    Point(double xx, double yy) {
        x = xx;
        y = yy;
    }
};
struct Line {
    Point s, e;
};
int sign(const double &x) {
    if(fabs(x) < eps) {
        return 0;
    }
    return x > 0? 1: -1;
}
bool operator<(const Point &a, const Point &b) {
    if(sign(a.x - b.x) == 0) {
        return a.y < b.y;
    }
    return a.x < b.x;
}
// 叉积
double operator^(const Point &a, const Point &b) {
    return a.x * b.y - a.y * b.x;
}
Point operator-(const Point &a, const Point &b) {
    return Point(a.x - b.x, a.y - b.y);
}
// 点积
double operator*(const Point &a, const Point &b) {
    return a.x * b.x + a.y * b.y;
}
// 计算两点距离
double dis(const Point &a, const Point &b) {
    return sqrt((a - b) * (a - b));
}

判断两线段是否相交(51nod 1264)

bool inter(Line l1, Line l2) {
    return max(l1.s.x, l1.e.x) >= min(l2.s.x, l2.e.x) &&
    max(l2.s.x, l2.e.x) >= min(l1.s.x, l1.e.x) &&
    max(l1.s.y, l1.e.y) >= min(l2.s.y, l2.e.y) &&
    max(l2.s.y, l2.e.y) >= min(l1.s.y, l1.e.y) &&
    sign((l2.s - l1.e) ^ (l1.s - l1.e)) * sign((l2.e - l1.e) ^ (l1.s - l1.e)) <= 0 &&
    sign((l1.s - l2.e) ^ (l2.s - l2.e)) * sign((l1.e - l2.e) ^ (l2.s - l2.e)) <= 0;
}

找到线段上离某点距离最近的点(51nod 1298)

Point NearestPointToLineSeg(Point p, Line l) {
    Point result;
    double t = ((p - l.s) * (l.e - l.s)) / ((l.e - l.s) * (l.e - l.s));
    if(t >= 0 && t <= 1) {
        result.x = l.s.x + (l.e.x - l.s.x) * t;
        result.y = l.s.y + (l.e.y - l.s.y) * t;
    } else {
        if(dis(p, l.s) < dis(p, l.e)) {
            result = l.s;
        } else {
            result = l.e;
        }
    }
    return result;
}

构造凸包(HDU 1392)

const int maxn = 200000 + 100;
int n, top;
Point point[maxn], sta[maxn];
// p 的数组下标为 [1, n]
// 构造的凸包存在 sta 里，从栈底到 top 点的顺序为逆时针
// 凸包上的点不存在三点共线和重复点
void ConvexHull(Point *p, int n) {
    top = 0;
    sort(p + 1, p + n + 1);
    for(int i = 1; i <= n; ++i) {
        while(top > 1 && ((sta[top - 1] - sta[top - 2]) ^ (p[i] - sta[top - 2])) <= 0) {
            --top;
        }
        sta[top++] = p[i];
    }
    int ttop = top;
    for(int i = n; i > 0; --i) {
        while(top > ttop && ((sta[top - 1] - sta[top - 2]) ^ (p[i] - sta[top - 2])) <= 0) {
            --top;
        }
        sta[top++] = p[i];
    }
    --top;
}

在三维空间内判断四点共面

将四个点构成的三个向量 $(x_1,y_1,z_1),(x_2,y_2,z_2),(x_3,y_3,z_3)$ 写成行列式：

$$\begin{vmatrix} x_1&y_1&z_1\\ x_2&y_2&z_2\\ x_3&y_3&z_3 \end{vmatrix}$$

计算行列式的值，若行列式的值为 $0$，则四点共面，否则不共面。

三角形外接圆半径

$$R=\frac{abc}{4S}$$

其中 $abc$ 分别为三边程度，$S$ 为三角形面积。