平面几何贪心或分类讨论

EnofTaiPeople · 2024-02-21 21:50:54 · 题解

既然这是一个平面几何贪心题，我们考虑分类讨论。

如果起点在直线外，那么它必须要分别到达直线端点，当它先到达直线的某一端时，直接沿直线走到另一端一定是最优策略，此时中间的点都被经过，于是只需考虑先走到那一端即可。

否则，起点在直线上。

从刚才的情况，我们发现，一旦到达直线外的点，就只有直线端点会对答案造成影响。

换言之，到达直线外的点之前，只有到达直线端点会对答案造成影响。

枚举会先到达哪个端点，但是，有可能先往中部走在到达这个端点更优。

事实上，我们需要枚举往中部走到的最远的点，也有可能先走到端点，再往中部走，在走出直线，容易发现这些计算都不复杂，除了中部点枚举之外都是 O(1) 的。

走到直线外之后问题就变成了最初的问题，依旧可以 O(1) 计算。

当然可能先把直线走完再走出去，但这些细节是平凡的：

ll k2(ll x){return x*x;}
struct dat{
    ll x,y;
    dat operator-(const dat &z)
    const{return{x-z.x,y-z.y};}
    void rd(){cin>>x>>y;}
    bool operator<(const dat &z)
    const{return x==z.x?y<z.y:x<z.x;}
    ll operator*(const dat &z)
    const{return x*z.y-y*z.x;}
    ld operator/(const dat &z)
    const{return sqrtl(k2(x-z.x)+k2(y-z.y));}
}a[N];
int n,m,K,b[N],bt;
ld ans,now;
int main(){
    ios::sync_with_stdio(false);
    int i,j,k,l,r,x,y,z;
    cin>>n>>K;
    for(x=1;x<=n;++x)a[x].rd();
    if(K!=1)swap(a[1],a[K]);
    for(i=2;i<n;++i)if((a[i]-a[1])*(a[n]-a[1]))b[++bt]=i;
    if(bt){
        if(bt==1)swap(a[b[1]],a[n]);
        else{
            if((a[b[1]]-a[1])*(a[b[2]]-a[1])){
                sort(a+2,a+n+1);
                printf("%.12Lf\n",min(a[1]/a[2],a[1]/a[n])+a[2]/a[n]);
                return 0;
            }
        }
    }
    for(k=K=1;k<n;++k)if(a[k]<a[1])++K;
    sort(a+1,a+n);
    ans=min(a[1]/a[n],a[n-1]/a[n])+a[1]/a[n-1]+a[K]/a[n];
    for(k=K;k<n;++k){
        now=min(a[K]/a[1]+a[k]/a[n],a[K]/a[k]+a[1]/a[n])+a[1]/a[k];
        if(k+1<n)now+=min(a[n]/a[k+1],a[n]/a[n-1])+a[k+1]/a[n-1];
        ans=min(ans,now);
    }
    K=n-K,reverse(a+1,a+n);
    for(k=K;k<n;++k){
        now=min(a[K]/a[1]+a[k]/a[n],a[K]/a[k]+a[1]/a[n])+a[1]/a[k];
        if(k+1<n)now+=min(a[n]/a[k+1],a[n]/a[n-1])+a[k+1]/a[n-1];
        ans=min(ans,now);
    }
    printf("%.12Lf\n",ans);
    return 0;
}