您现在的位置：程式碼之家 >> 編程語言 > >> C語言 >> C++ >> C++ 入門

四邊形費馬點問題：尋找最小距離和的頂點

編輯：C++ 入門

四邊形費馬點問題：尋找最小距離和的頂點

在幾何學中，三角形的費馬點（又稱托里切利點）是使三個頂點到該點距離之和最小的點。那麼，四邊形是否存在類似的點？如果存在，該如何求解？本文將探討四邊形費馬點的尋找方法，並提供完整的算法實現。

問題描述

給定一個四邊形的四個頂點坐標，要求找到一個點，使得從這四個頂點到該點的總距離最小。這就是四邊形的費馬點問題。輸入包含多組測試數據，每組包含八個浮點數，依次表示四個頂點的 x、y 坐標。輸入以八個 -1 結束。對於每組數據，輸出最小總距離，保留小數點後四位。

算法思路

四邊形費馬點的性質與三角形不同。對於凸四邊形，費馬點即為兩條對角線的交點；對於凹四邊形，費馬點則位於凹角的頂點上。因此，解決思路如下：

計算四個頂點兩兩之間的距離和，作為候選答案之一（對應頂點作為費馬點的情況）。
判斷四邊形是凸還是凹：通過向量叉積檢查對角線是否相交。
若對角線相交（凸四邊形），計算對角線交點，並求出該點到四頂點的距離和。
若對角線不相交（凹四邊形），費馬點即為凹角頂點，其距離和已在步驟 1 中計算。
取上述所有候選值中的最小值作為答案。

幾何判斷與交點計算

利用向量叉積判斷兩線段是否相交。對於線段 AB 和 CD，若叉積 cross(A,B,C) * cross(A,B,D) < 0 且 cross(C,D,A) * cross(C,D,B) < 0，則相交。本題中，只需檢查三組對角線配對：(1,2)-(3,4)、(1,3)-(2,4)、(1,4)-(2,3)。若某組相交，即為凸四邊形，求其交點。

交點計算使用直線標準方程 ax + by + c = 0，通過克拉默法則求解線性方程組。

代碼實現（C++）

#include <stdio.h>
#include <math.h>
#include <string.h>

const double EPS = 1e-8;

struct Point { double x, y; } p[5];
struct Line { double a, b, c; };

double dist(Point a, Point b) {
    return sqrt((a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y));
}

int dblcmp(double d) {
    if (fabs(d) < EPS) return 0;
    return d > 0 ? 1 : -1;
}

double cross(Point a, Point b, Point c) {
    return (b.x-a.x)*(c.y-a.y) - (b.y-a.y)*(c.x-a.x);
}

void lineFromPoints(double x1, double y1, double x2, double y2, Line &l) {
    l.a = y2 - y1;
    l.b = x1 - x2;
    l.c = x2*y1 - x1*y2;
}

void lineIntersect(Line l1, Line l2, double &x, double &y) {
    double d = l1.a*l2.b - l2.a*l1.b;
    x = (l2.c*l1.b - l1.c*l2.b) / d;
    y = (l1.c*l2.a - l2.c*l1.a) / d;
}

int main() {
    int i, j;
    double vertexSum[5] = {0}, ans, fx, fy;
    Point fermat;

    while (true) {
        bool hasData = false;
        for (i = 1; i <= 4; i++) {
            scanf("%lf%lf", &p[i].x, &p[i].y);
            if (p[i].x != -1 || p[i].y != -1) hasData = true;
        }
        if (!hasData) break;

        // 計算各頂點到其他三頂點的距離和
        for (i = 1; i <= 4; i++) {
            vertexSum[i] = 0;
            for (j = 1; j <= 4; j++) vertexSum[i] += dist(p[i], p[j]);
        }

        Line l1, l2;
        bool found = false;

        // 檢查三組對角線
        if (cross(p[1],p[2],p[3]) * cross(p[1],p[2],p[4]) < 0) {
            lineFromPoints(p[1].x,p[1].y,p[2].x,p[2].y,l1);
            lineFromPoints(p[3].x,p[3].y,p[4].x,p[4].y,l2);
            lineIntersect(l1, l2, fx, fy);
            found = true;
        } else if (cross(p[1],p[3],p[4]) * cross(p[1],p[3],p[2]) < 0) {
            lineFromPoints(p[1].x,p[1].y,p[3].x,p[3].y,l1);
            lineFromPoints(p[2].x,p[2].y,p[4].x,p[4].y,l2);
            lineIntersect(l1, l2, fx, fy);
            found = true;
        } else if (cross(p[1],p[4],p[3]) * cross(p[1],p[4],p[2]) < 0) {
            lineFromPoints(p[1].x,p[1].y,p[4].x,p[4].y,l1);
            lineFromPoints(p[2].x,p[2].y,p[3].x,p[3].y,l2);
            lineIntersect(l1, l2, fx, fy);
            found = true;
        }

        ans = 1e100;
        if (found) {
            fermat.x = fx; fermat.y = fy;
            double sum = 0;
            for (i = 1; i <= 4; i++) sum += dist(fermat, p[i]);
            ans = sum;
        }

        // 比較頂點距離和
        for (i = 1; i <= 4; i++) if (vertexSum[i] < ans) ans = vertexSum[i];

        printf("%.4lf\n", ans);
    }
    return 0;
}