美丽的桥梁

Posted on Edited on In

美丽的桥梁

可以得到一个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");
}