WA on 8求调
  • 板块P1663 山
  • 楼主Vicem
  • 当前回复2
  • 已保存回复2
  • 发布时间2024/11/26 18:50
  • 上次更新2024/11/26 20:40:27
查看原帖
WA on 8求调
973373
Vicem楼主2024/11/26 18:50

19999.000000 输出是 26750.680000 (我保留了两位小数)

const int N=5e3+7,M=2e6+7;
const int inf=0x3f3f3f3f;
int n,m,Q,T;
db x[N],y[N];
db k[N],b[N];
bool check(db mid) {
	db L=-2e9,R=2e9;
	rep(i,2,n) {
		if(k[i]<0) L=max(L,(mid-b[i])/k[i]);
		if(k[i]>0) R=min(R,(mid-b[i])/k[i]);
		if((int)(k[i])==0&&mid<b[i]) return false;
	}
	return L<=R;
}
int main( ) {
	basic_ios<char>::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin>>n;
	cin>>x[1]>>y[1];
	rep(i,2,n) {
		cin>>x[i]>>y[i];
		k[i]=(y[i]-y[i-1])/(x[i]-x[i-1]+eps);
		b[i]=y[i]-k[i]*x[i];
	}
	db l=0,r=1e6,ans;
	while(r-l>=eps) {
		db mid=(l+r)/2;
		if(check(mid)) r=mid-eps,ans=mid;
		else l=mid+eps;
	}
	cout<<fixed<<setprecision(2)<<ans<<'\n';
	return 0;
}

2024/11/26 18:50
加载中...