線分 \(S-T\) が \(C\) と交点を持たないとき、明らかに答えは \(S-T\) の距離と一致します。以下そうでないときを考えます。

そのような場合、 移動は以下の方法しか考えなくてよいです。

• \(S\) から \(C\) 上のある頂点 \(x\) に直線で移動 \(\to\) \(C\) 上のある頂点 \(x\) から \(C\) 上の別のある頂点 \(y\) まで \(C\) の周上を通って移動 \(\to\) \(C\) 上の別のある頂点 \(y\) から \(T\) に直線で移動

正当性は、それ以外の経路を考えたときに上記の方法に変化させることで距離が短くなることから従います。

さらに、このような頂点 \(x,y\) の候補としてはできる限りぎりぎりのところ（すなわち、 \(S\) から \(x\) に直線で移動する際には \(C\) の内部を通らないが、\(S\) から \(x\) に \(C\) で隣接する頂点の一方 \(x'\) に直線で移動する際には \(C\) の内部を通ってしまう、\(y\) についても同様）のみを考えて損をしません。この正当性は明らかです。

このようなぎりぎりの頂点 \(x,y\) の見つけ方は様々な方法が考えられますが、実装が容易なのは \(C,S,T\) の凸包を求めることでしょう。

結局、移動方法としては \(C,S,T\) の凸包をとり、その周上を移動するもののみ考えればよいです。 時計回りと反時計回りを試し、小さいほうが答えとなります。このアルゴリズムは \(O(N)\) で動作します。

実装例(c++):

#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using point = pair<ll, ll>;

long double dist(point a, point b) {
    return hypot<long double>(a.first - b.first, a.second - b.second);
}

ll cross(point o, point a, point b) {
    return (a.first - o.first) * (b.second - o.second) - (a.second - o.second) * (b.first - o.first);
}

vector<point> convex_hull(vector<point> ps) {
    int n = ps.size();
    sort(ps.begin(), ps.end());
    vector<point> ret;
    for(auto p : ps) {
        while((int)ret.size() >= 2 and cross(ret.end()[-1], ret.end()[-2], p) >= 0)
            ret.pop_back();
        ret.push_back(p);
    }
    int t = ret.size();
    for(int i = n - 2; i >= 0; --i) {
        auto p = ps[i];
        while((int)ret.size() > t and cross(ret.end()[-1], ret.end()[-2], p) >= 0)
            ret.pop_back();
        ret.push_back(p);
    }
    return ret;
}

long double ans, d1, d2;
int main() {
    int n;
    cin >> n;
    vector<point> c(n + 2);
    for(int i = 0; i < n + 2; i++) cin >> c[i].first >> c[i].second;
    point s = c.end()[-2], t = c.end()[-1];
    auto ch = convex_hull(c);
    int k = ch.size();
    int sid = -1, tid = -1;
    for(int i = 0; i < k; i++) {
        if(ch[i] == s) sid = i;
        if(ch[i] == t) tid = i;
    }
    if(min(sid, tid) == -1)
        ans = dist(s, t);
    else {
        for(int i = sid; i != tid; i = (i + 1) % k)
            d1 += dist(ch[i], ch[(i + 1) % k]);
        for(int i = tid; i != sid; i = (i + 1) % k)
            d2 += dist(ch[i], ch[(i + 1) % k]);
        ans = min(d1, d2);
    }
    cout << setprecision(15) << ans << endl;
}