牛客挑战赛33-C艾伦的立体机动装置(三分)

题目思路

因为下表面是可以走的，所以不能直接算s点和t点的直线距离。这个时候就要考虑枚举经过下表面的每一条边，再在每条边上三分求出最短距离。注意最短距离的初始值要设为不经过下表面任何一条边的最短距离。复杂度O（nlogn）

slen记录每个顶点到s点的距离，getdis是获得上表面或下表面的两点距离，finddis是获得如果经过下表面某个点的路程距离，tridiv三分。因为我的下标是从0开始的，所以s点是p[s-1]。

#include<bits/stdc++.h>
#define ll long long
using namespace std;
int s,t,n;
double ans,slen[100001],h;
pair<double,double>p[100001];
inline double getdis(pair<double,double>p1,pair<double,double>p2)
{
    return sqrt((p1.first-p2.first)*(p1.first-p2.first)+(p1.second-p2.second)*(p1.second-p2.second));
}
inline double finddis(pair<double,double>now,int l,int r)
{
    double len = min(slen[l]+getdis(p[l],now),slen[r]+getdis(p[r],now));
    return sqrt(h*h+len*len)+getdis(now,p[t-1]);
}
inline double tridiv(int l,int r)
{
    double minn = 0x3f3f3f3f;
    pair<double,double> left = p[l];
    pair<double,double> right = p[r];
    while(getdis(left,right)>1e-3)
    {
        pair<double,double> first = make_pair((2*left.first+right.first)/3,(2*left.second+right.second)/3);
        pair<double,double> second = make_pair((left.first+2*right.first)/3,(left.second+2*right.second)/3);
        double firdis = finddis(first,l,r);
        double secdis = finddis(second,l,r);
        if(firdis>secdis)
        {
            left = first;
            minn = min(minn,secdis);
        }
        else
        {
            right = second;
            minn = min(minn,firdis);
        }
    }
    return minn;
}
int main()
{
    scanf("%d%lf",&n,&h);
    for(int i = 0;i<n;i++)
        scanf("%lf%lf",&p[i].first,&p[i].second);
    scanf("%d%d",&s,&t);
    double s1 = 0,s2 = 0,sum = 0;
    int last = s-1;
    slen[last] = 0;
    for(int i = s%n;i!=s-1;i++,i%=n)
    {
        double len = getdis(p[last],p[i]);
        sum+=len;
        slen[i] = slen[last]+len;
        last = i;
    }
    sum+=getdis(p[last],p[s-1]);
    for(int i = 0;i<n;i++)
        slen[i] = min(slen[i],sum-slen[i]);
    ans = sqrt(slen[t-1]*slen[t-1]+h*h);
    last = n-1;
    for(int i = 0;i<n;i++,last++,last%=n)
        ans = min(ans,tridiv(last,i));
    printf("%.6lf",ans);
    return 0;
}