C++14(g++5.4) 解法, 执行用时: 265ms, 内存消耗: 2016K, 提交时间: 2019-10-19 15:04:58

#include<bits/stdc++.h>

typedef long long ll;
using namespace std;
const int INF = 0x3f3f3f3f;
const ll LLINF = 0x3f3f3f3f3f3f3f3f;
const int MAXN = 2e5 + 5;
const ll mod = 1e9 + 7;
const double eps = 1e-6;
int n, s, t;
double x[MAXN], y[MAXN], h;

double getdis(int i, int j) {
    return sqrt((x[i] - x[j]) * (x[i] - x[j]) + (y[i] - y[j]) * (y[i] - y[j]));
}

double cal(double now, int nowpos, int prepos, double carry) {
    double dx = x[nowpos] - x[prepos];
    double dy = y[nowpos] - y[prepos];
    double xx = x[prepos] + dx * now;
    double yy = y[prepos] + dy * now;
    carry += getdis(nowpos, prepos) * now;
    double ans1 = sqrt(carry * carry + h * h);
    double ans2 = sqrt((xx - x[t]) * (xx - x[t]) + (yy - y[t]) * (yy - y[t]));
    return ans1 + ans2;
}

double getans(int delta) {
    double ans = h + getdis(s, t);
    double carry = 0;
    int nowpos = s;
    int prepos = s;
    do {
        prepos = nowpos;
        nowpos += delta, nowpos %= n, nowpos += n, nowpos %= n;
        double l = 0, r = 1, midl, midr;
        while (r - l > eps) {
            double delta = (r - l) / 3;
            midl = l + delta;
            midr = midl + delta;
            if (cal(midl, nowpos, prepos, carry) >= cal(midr, nowpos, prepos, carry))l = midl;
            else r = midr;
        }
        ans = min(ans, cal(l, nowpos, prepos, carry));
        carry += getdis(nowpos, prepos);
    } while (prepos != t);
    return ans;
}

int main() {
    scanf("%d%lf", &n, &h);
    for (int i = 0; i < n; i++)scanf("%lf%lf", &x[i], &y[i]);
    scanf("%d%d", &s, &t), s--, t--;
    double ans = min({getans(1), getans(-1)});
    printf("%.6f\n", ans);
    return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 519ms, 内存消耗: 1912K, 提交时间: 2020-03-14 16:02:11

#include<bits/stdc++.h>
using namespace std;
typedef double D;
int n,h,s,t;
D a[100007],b[100007],ans=1e18;
D dis(D x,D y,D xx,D yy)
{
	return sqrt((x-xx)*(x-xx)+(y-yy)*(y-yy));
}
void work(int ad)
{
	D len=0;
	int p=s;
	while(p!=t)
	{
		D val=dis(a[p],b[p],a[(p+ad+n)%n],b[(p+ad+n)%n]);
		for(int i=0;i<=100;++i)
		{
			D XX=a[p]+(a[(p+ad+n)%n]-a[p])*i/100;
			D YY=b[p]+(b[(p+ad+n)%n]-b[p])*i/100;
			ans=min(ans,dis(0,h,len+val*i/100,0)+dis(a[t],b[t],XX,YY));
		}
		len+=val,p=(p+ad+n)%n;
	}
}
int main()
{
	cin>>n>>h;
	for(int i=0;i<n;++i)
	cin>>a[i]>>b[i];
	cin>>s>>t,s--,t--;
	work(1),work(-1);
	cout<<ans;
}