求助斜率优化
  • 板块学术版
  • 楼主大眼仔Happy
  • 当前回复3
  • 已保存回复3
  • 发布时间2023/11/7 15:40
  • 上次更新2023/11/7 18:32:57
查看原帖
求助斜率优化
537046
大眼仔Happy楼主2023/11/7 15:40

rt,k是一个计算斜率的函数,其他的先不需要管

求助大佬

for(int i=1;i<=n;i++)
{
	ll yA=y[i]-R,yB=y[i]-L;
	pl=GetPL(yA);pr=GetPR(yB);
	
	if(pl>pr){calc(yA,yB,i);continue;}
	else calc(yA,y[pl],i),calc(y[pr],yB,i);
	
	while(h<=t&&q[h]<pl)h++;
	while(p<pl-1)p++;
	while(p<pr){p++;while(h<t&&K(q[t-1],q[t])<K(q[t],p))t--;q[++t]=p;}
	
	for(int j=pl;j<=pr;j++)ans=max(ans,K(j,i));//this
}
2023/11/7 15:40
加载中...