计算几何半平面交铁人三项

Question

刘汝佳的训练指南上铁人三项的代码中

if (fabs(a) > fabs(b)) P = Point(-c / a, 0);
else P = Point(0, -c / b);

到底为什么啊，同一条直线选点不同不应该对结果没影响吗，是我学的不对吗
完整代码：

#include<iostream>
#include<cmath> 
#include<algorithm>
using namespace std;
const double eps = 1e-8;
const int inf = 0x3f3f3f3f;
struct Point {
    double x, y;
    Point(double x = 0, double y = 0) :x(x), y(y) {}
}p[105], poly[105];
int n;
typedef Point Vector;
Vector operator + (Vector A, Vector B) {
    return Vector(A.x + B.x, A.y + B.y);
}
Vector operator - (Point A, Point B) {
    return Vector(A.x - B.x, A.y - B.y);
}
Vector operator * (Vector A, double p) {
    return Vector(A.x * p, A.y * p);
}
int sgn(double x) {
    if (fabs(x) < eps)
        return 0;
    if (x < 0)
        return -1;
    return 1;
}
double Dot(Vector A, Vector B) {
    return A.x * B.x + A.y * B.y;
}
double Cross(Vector A, Vector B) {
    return A.x * B.y - A.y * B.x;
}
double Length(Vector A) {
    return sqrt(Dot(A, A));
}
Vector Normal(Vector A) {
    double L = Length(A);
    return Vector(-A.y / L, A.x / L);
}
struct Line {
    Point p;
    Vector v;
    double ang;
    Line() {}
    Line(Point p, Vector v) : p(p), v(v) {
        ang = atan2(v.y, v.x);
    }
    bool operator < (const Line& L) const {
        return ang < L.ang;
    }
}L[105];
bool OnLeft(Line L, Point p) {
    return Cross(L.v, p - L.p) >= 0;
}
Point GetIntersection(Line a, Line b) {
    Vector u = a.p - b.p;
    double t = Cross(b.v, u) / Cross(a.v, b.v);
    return a.p + a.v * t;
}
int HalfplaneIntersection(Line* L, int n, Point* poly) {
    sort(L, L + n);
    int fst = 0, lst = 0;
    Point* P = new Point[n];
    Line* q = new Line[n];
    q[fst = lst = 0] = L[0];
    for (int i = 1; i < n; ++i) {
        while (fst < lst && !OnLeft(L[i], P[lst - 1])) --lst;
        while (fst < lst && !OnLeft(L[i], P[fst])) ++fst;
        q[++lst] = L[i];
        if (sgn(Cross(q[lst].v, q[lst - 1].v)) == 0) {
            --lst;
            if (OnLeft(q[lst], L[i].p)) q[lst] = L[i];
        }
        if (fst < lst)
            P[lst - 1] = GetIntersection(q[lst - 1], q[lst]);
    }
    while (fst < lst && !OnLeft(q[fst], P[lst - 1])) --lst;
    if (lst - fst <= 1) return 0;
    P[lst] = GetIntersection(q[lst], q[fst]);
    int m = 0;
    for (int i = fst; i <= lst; ++i) poly[m++] = P[i];
    return m;
}
int u[105], v[105], w[105];
int main() {
    int n;
    while (~scanf("%d", &n) && n) {
        for (int i = 0; i < n; i++)
            scanf("%d%d%d", &v[i], &u[i], &w[i]);
        for (int i = 0; i < n; i++) {
            int flag = 1, cnt = 0;
            double k = 10000;
            for (int j = 0; j < n; j++) {
                if (i != j) {
                    if (v[i] <= v[j] && u[i] <= u[j] && w[i] <= w[j]) {
                        flag = 0;
                        break;
                    }
                    if (v[i] >= v[j] && u[i] >= u[j] && w[i] >= w[j]) 
                        continue;
                    double a = (k / v[j] - k / w[j]) - (k / v[i] - k / w[i]);
                    double b = (k / u[j] - k / w[j]) - (k / u[i] - k / w[i]);
                    double c = k / w[j] - k / w[i];
                    Point P;
                    Vector v(b, -a); 
                    if (fabs(a) > fabs(b)) P = Point(-c / a, 0);
                    else P = Point(0, -c / b);
                    L[cnt++] = Line(P, v);
                }
            }
            if (flag) { 
                L[cnt++] = Line(Point(0, 0), Vector(0, -1));
                L[cnt++] = Line(Point(0, 0), Vector(1, 0));
                L[cnt++] = Line(Point(0, 1), Vector(-1, 1));
                if (!HalfplaneIntersection(L, cnt, poly)) flag = 0;
            }
            if (flag) printf("Yes\n");
            else printf("No\n");
        }
    }
    return 0;
}

Answer 1

代码好长啊你的，看一下相关的解释，部分分析来源GPT参考

在代码中，对于每个给定的三维点 (v[i], u[i], w[i])，它判断该点是否在其余点构成的三维凸包内部。

在具体计算半平面交时，代码中涉及到对于平面方程 ax + by + c = 0 中，如果 fabs(a) > fabs(b)，则取 P = Point(-c / a, 0)，否则取 P = Point(0, -c / b)。

这段代码的目的是选择平面上的一个点作为半平面交的起始点。对于给定的平面 ax + by + c = 0，选取 (x, y)，当 fabs(a) > fabs(b) 时，意味着平面更接近于垂直于 x 轴的方向，所以选取 P = Point(-c / a, 0)，即该平面与 x 轴的交点；当 fabs(b) > fabs(a) 时，意味着平面更接近于垂直于 y 轴的方向，所以选取 P = Point(0, -c / b)，即该平面与 y 轴的交点。这个选取的点用于辅助计算半平面交。

在算法中，选择不同的起始点可能会对结果产生微小影响，但在半平面交问题中，选择合适的起始点能更好地确保算法的正确性和稳定性。因此，选择合适的起始点可以帮助更好地进行半平面交的计算，但在这个问题的实现中，代码所选择的起始点并不是半平面交算法的核心点，它更多地是为了辅助计算而已。