自动搬运

查看原文

来自洛谷，原作者为

	FjswYuzu Rainybunny狂热粉丝!111111 | Last Goodbye

搬运于2025-08-24 22:19:02，当前版本为作者最后更新于2022-09-13 16:41:49，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

其实是数学题。先猜个 $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;
}