数学荣获 74 分，是为波特

· · 题解

其实是数学题。先猜个 O(n^2) 复杂度。

然后你发现判定每个区间是否合法并不好做……如果是双指针发现后面又不存在单调性。

那可以考虑拆成两半，算一下每个点为左端点前半的半圆能延伸到多远，作为右端点同理（因为发现只考虑一半的话，随着半径增加，每个坐标上需要的空间也是增加的），分别记为 L_i,R_i。

那判定一个区间是否合法就比较容易了。问题在怎么求这个 L_i,R_i。以求 L_i 为例：

当前正在算 L_i，枚举后面的每个 j 来更新 L_i。假设我们的半圆半径为 r，它跨过了 x_j 这个位置。首先有圆心坐标 (x_i+r,h-r)，其到 d=(x_j,y_j) 的距离为 \sqrt{(x_i+r-x_j)^2+(h-r-y_j)^2}。d \leq r 和 h-r\geq y_j 两个条件中至少满足两个。第二个条件很好处理，第一个条件可以解一元二次方程将根求出来。这两种情况求并之后可以知道想要覆盖 (x_j,y_j) 且不冲突能够使用的最大的半径 R，然后令 L_i \gets \min(L_i,R) 即可。

LL n,A,B;
LL dp[10005];
DB L[10005],R[10005];
DB x[10005],y[10005],h;
int main(){
    n=read(),h=read(),A=read(),B=read();
    for(LL i=1;i<=n;++i)    x[i]=read(),y[i]=read();
    for(LL i=1;i<=n;++i)
    {
        L[i]=min((x[n]-x[i])/2,h-y[i]);
        for(LL j=i+1;j<=n;++j)
        {
            if(x[j]-x[i]>L[i])  break;
            DB r1=h-y[j];
            DB a=1,b=2*x[i]-2*x[j]-2*h+2*y[j],c=(x[i]-x[j])*(x[i]-x[j])+(h-y[j])*(h-y[j]);
            DB r2=(-b+sqrt(b*b-4*a*c))/(2*a);
            L[i]=min(L[i],max(r1,r2));
        }
        L[i]*=2;
    }
    for(LL i=1;i<=n;++i)
    {
        R[i]=min((x[i]-x[1])/2,h-y[i]);
        for(LL j=i-1;j;--j)
        {
            if(x[i]-x[j]>R[i])  break;
            DB r1=h-y[j];
            DB a=1,b=2*x[j]-2*x[i]-2*h+2*y[j],c=(x[i]-x[j])*(x[i]-x[j])+(h-y[j])*(h-y[j]);
            DB r2=(-b+sqrt(b*b-4*a*c))/(2*a);
            R[i]=min(R[i],max(r1,r2));
        }
        R[i]*=2;
    }
    memset(dp,63,sizeof dp);
    dp[1]=A*(LL(h)-y[1]);
    for(LL i=2;i<=n;++i)    for(LL j=1;j<i;++j) if(x[j]+L[j]>=x[i] && x[i]-R[i]<=x[j])  dp[i]=min(dp[i],dp[j]+A*(LL(h)-(LL)y[i])+LL((LL)x[i]-(LL)x[j])*((LL)x[i]-(LL)x[j])*B);
    if(dp[n]==dp[0])    puts("impossible");
    else    write(dp[n]),puts("");
    return 0;
}