美丽的桥梁

可以得到一个Naive的暴力方法来判断在$(L,R)$上修桥是否合法:

显然的性质: 如果有相交，则一定存在一个关键点相交

设得到的圆半径为$r=\frac{x_R-x_L} {2}$，圆心为$(x,y)=(\frac{x_L+x_R} {2},h-r)$

枚举每个$i\in [L,R]$判断是否点$x_i,y_i$是否相交，如果相交，只需要满足

$y_i>y$，且 其与圆心距离$>r$

考虑优化判断，将生成的拱形分为左右两部分，分别考虑即可

推论: 对于每个$L$，其左半边不相交的半径为描述为一个范围$[0,A_L]$

同理的，对于每个$R$也是如此，能求得一个范围$[0,B_R]$

考虑对于每个$L$，枚举每个$i>L$ 来求出$A_L$

设半径为$r$，列出圆心与点$x_i,y_i$距离的表达式，必须满足距离$\leq r$，就能得到一个二次方程

二次方程的解集为$x_1,x_2$，但是实际上$[0,x_1]$这一段不满足$y_i>y$，因此也是合法的

即将每次求得的$[0,x_2]$区间取交集即可

复杂度为$O(n^2)$

同理求得每个$B_R$

考虑朴素的dp，令$dp_i$表示解决了$[1,i]$前缀的最小代价

枚举$j$，$O(1)$判断$(i,j)$是否合法，然后进行转移

tips: 题目的代价计算方法可能没讲清楚。。。

复杂度为$O(n^2)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize(2)
typedef double db;
typedef long long ll;
#define rep(i,a,b) for(int i=a,i##end=b;i<=i##end;++i)
#define drep(i,a,b) for(int i=a,i##end=b;i>=i##end;--i)
template <class T> inline void cmin(T &a,const T &b){ ((a>b)&&(a=b)); }
template <class T> inline void cmax(T &a,const T &b){ ((a<b)&&(a=b)); }

char IO;
template <class T=int> T rd(){
	T s=0; int f=0;
	while(!isdigit(IO=getchar())) if(IO=='-') f=1;
	do s=(s<<1)+(s<<3)+(IO^'0');
	while(isdigit(IO=getchar()));
	return f?-s:s;
}

const int N=1e4+10;
const db eps=1e-9;
const ll INF=4e18;

int n,h,a,b;
int X[N],Y[N];
db L[N],R[N];
db Sqr(db x){ return x*x; }
ll dp[N];

int main(){
	n=rd(),h=rd(),a=rd(),b=rd();
	rep(i,1,n) X[i]=rd(),Y[i]=rd();
	rep(i,1,n) {
		L[i]=min((db)(X[n]-X[i])/2,(db)(h-Y[i]));
		rep(j,i+1,n) {
			if(X[j]-X[i]>L[i]+eps) break;
			db a=1,b=2*(X[i]-X[j]+Y[j]-h),c=Sqr(X[i]-X[j])+Sqr(Y[j]-h);
			db d=sqrt(b*b-4*a*c);
			db r=(-b+d)/(2*a);
			cmin(L[i],r);
		}
		L[i]*=2;
	}
	rep(i,1,n) {
		R[i]=min((db)(X[i]-X[1])/2,(db)(h-Y[i]));
		drep(j,i-1,1) {
			if(X[i]-X[j]>R[i]+eps) break;
			db a=1,b=2*(X[j]-X[i]+Y[j]-h),c=Sqr(X[j]-X[i])+Sqr(Y[j]-h);
			db d=sqrt(b*b-4*a*c);
			db r=(-b+d)/(2*a);
			cmin(R[i],r);
		}
		R[i]*=2;
	}
	dp[1]=1ll*a*(h-Y[1]);
	rep(i,2,n) {
		dp[i]=INF;
		drep(j,i-1,1) {
			if(X[i]-X[j]>R[i]+eps) break;
			if(X[i]-X[j]>L[j]+eps) continue;
			cmin(dp[i],dp[j]+1ll*a*(h-Y[i])+1ll*(X[i]-X[j])*(X[i]-X[j])*b);
		}
	}
	if(dp[n]<INF) printf("%lld\n",dp[n]);
	else puts("impossible");
}