关于h[i]=h[j]时的斜率判断

P4655 [CEOI2017] Building Bridges

ZhuMingYang @ 2020-06-28 23:14:52

如果不加$h_i=h_j$的特判则25分如果特判$h_i=h_j$返回inf 则65分如果特判$h_i=h_j$下面代码`dp[i]+h[i]*h[i]-sum[i]<dp[j]+h[j]*h[j]-sum[j]`的`<`改为`>` 则35分只有下面这样写才AC 就很谜 ```cpp inline double slope(int i,int j) { if(h[i]==h[j]) { if(dp[i]+h[i]*h[i]-sum[i]<dp[j]+h[j]*h[j]-sum[j]) return inf; else return -inf; } return (double)((dp[i]+h[i]*h[i]-sum[i])-(dp[j]+h[j]*h[j]-sum[j]))/(h[i]-h[j]); } ``` [完整代码](https://www.luogu.com.cn/paste/ojmsplpp)

by ZhuMingYang @ 2020-06-28 23:17:33

所以斜率优化碰到x值相等的情况怎么办。。。

不过叉积似乎不影响？

by AzusaCat @ 2020-06-29 07:15:38

x值相等根据题目保留y最小/大的那个

by wind_whisper @ 2021-11-12 00:58:13

我是在splay加点里面特判的（如果你写的也是splay的话）

while(1){
    if(dx[now]==x){
        if(dy[now]<y) return;
        dy[now]=y;id[now]=idx;xx=now;break;
    }
    else if(tr[now][x>dx[now]]) now=tr[now][x>dx[now]];
    else{
        tr[now][x>dx[now]]=New(now,x,y,idx);
        xx=tot;
        break;
    }
}