题解：P1027 [NOIP 2001 提高组] Car 的旅行路线

Retoayd · 2025-06-21 22:18:42 · 题解

这道题硬控我 1 小时。。。

题目难点：

主要是输入只告诉了我们三个点的坐标，所以需要求第四个点的坐标，要是每种情况都讨论一边的话代码比较长（但也能做），所以推荐写循环。剩下的就是最短路了，这里用 Floyd 就行了。

求第四点的方法：

初中数学中我们学到了两点间距离公式，中点公式和勾股定理，运用这三点，就能求出第四点的坐标了。
代码实现：

void work(int xx) {
    int ap, bp, cp; //cp代表直角三角形中斜边所对应的点，ap和bp代表另外两点
    for(int i = 0; i <= 2; i++) {
        for(int j = 0; j <= 2; j++) {
            for(int l = 0; l <= 2; l++) {
                if(i == j || j == l || i == l) continue;
                double ka = dis2(a[xx].x[i], a[xx].y[i], a[xx].x[j], a[xx].y[j]);
                double kb = dis2(a[xx].x[j], a[xx].y[j], a[xx].x[l], a[xx].y[l]);
                double kc = dis2(a[xx].x[i], a[xx].y[i], a[xx].x[l], a[xx].y[l]);
                if(ka + kb == kc) ap = l, bp = i, cp = j; //勾股定理判断是否构成直角三角形
                else continue;
            } 
        }
    }
    double midx = (a[xx].x[ap] + a[xx].x[bp]) / 2.0, midy = (a[xx].y[ap] + a[xx].y[bp]) / 2.0;
    midx *= 2, midy *= 2;
    newx = midx - a[xx].x[cp], newy = midy - a[xx].y[cp];
    return;
}

最重要的一点，这里求两点间距离的 dis2 函数千万不要开根号，不然会有精度损失，导致没有答案。