A.

D. Carl’s Vacation

可以联想到将军饮马模型。我们把三维的金字塔侧面展平到二维上，那么答案的最短路径就可以表达为

tip1→foot1→foot2→top2 tip_1\to foot_1\to foot_2\to top_2

于是，我们可以枚举每个金字塔的四个侧面，共 4×4=164\times 4=16 种情况，在每种情况里求最短路径即可。

接下来考虑如何求这个最短路径。我们肯定需要找到两个 footfoot 的坐标。考虑用向量的模长表示线段长度，以及将两个 footfoot 的定比分点作为变量的话，那么路径长度 f(k1,k2)f(k_1,k_2) 分别关于 k1,k2k_1,k_2 是单峰函数，所以可以三分套三分。

小细节：浮点数三分或者二分的话，可以指定二分次数，而非 l,rl,r 相差 eps\texttt{eps}，后者容易出现浮点误差。

Code
 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
#include "headers/geometry.hpp"
#include <iostream>

using namespace Geo2D;
using namespace std;

Point p1[4], p2[4], tip1, tip2;
Decimal h1, h2, d1, d2, len1, len2;

Decimal phi = 0.618, cphi = -phi + 1;

int main() {
    cin >> p1[0] >> p1[1] >> h1;
    cin >> p2[0] >> p2[1] >> h2;
    for (int i = 2; i < 4; i++) {
        p1[i] = p1[i - 1] + (p1[i - 1] - p1[i - 2]).Perp();
        p2[i] = p2[i - 1] + (p2[i - 1] - p2[i - 2]).Perp();
    }
    tip1 = (p1[0] + p1[2]) / 2;
    tip2 = (p2[0] + p2[2]) / 2;
    len1 = p1[0].Distance(p1[1]);
    len2 = p2[0].Distance(p2[1]);
    d1   = (len1.sqr() / 4 + h1.sqr()).sqrt();
    d2   = (len2.sqr() / 4 + h2.sqr()).sqrt();

    Decimal ans = 2e18;

    for (int i = 0; i < 4; i++) {
        Vector v1   = p1[(i + 1) % 4] - p1[i];
        Point midp1 = (p1[i] + p1[(i + 1) % 4]) / 2;
        Point pt1   = midp1 + v1.Normal() * d1;

        for (int j = 0; j < 4; j++) {
            Vector v2   = p2[(j + 1) % 4] - p2[j];
            Point midp2 = (p2[j] + p2[(j + 1) % 4]) / 2;
            Point pt2   = midp2 + v2.Normal() * d2;

            Decimal precent_l1 = 0;
            Decimal precent_r1 = 1;

            auto findfoot1 = [&](Decimal precent_mid1) -> Decimal {
                Point foot1        = p1[i] + v1 * precent_mid1;
                Decimal precent_l2 = 0;
                Decimal precent_r2 = 1;

                auto findfoot2 = [&](Decimal precent_mid2) -> Decimal {
                    Point foot2 = p2[j] + v2 * precent_mid2;
                    return foot1.Distance(foot2) + foot1.Distance(pt1) +
                           foot2.Distance(pt2);
                };

                for (int __ = 1; __ <= 100; __++) {
                    Decimal l2 = precent_l2 * phi + precent_r2 * cphi;
                    Decimal r2 = precent_l2 * cphi + precent_r2 * phi;

                    if (findfoot2(l2) > findfoot2(r2)) precent_l2 = l2;
                    else precent_r2 = r2;
                }

                return findfoot2(precent_l2);
            };

            for (int _ = 1; _ <= 100; _++) {
                Decimal l1 = precent_l1 * phi + precent_r1 * cphi;
                Decimal r1 = precent_l1 * cphi + precent_r1 * phi;
                if (findfoot1(l1) > findfoot1(r1)) precent_l1 = l1;
                else precent_r1 = r1;
            }

            ans = min(ans, findfoot1(precent_l1));
        }
    }

    std::cout << ans << '\n';
}