静态维护凸包
动态维护凸包
Splay平衡树
维护每个点向左、向右的线段的斜率\(lp,rp\)（初始为\(INF\)和\(-INF\)方便插入）
插入一个点时，先加入Splay，再向左右找到最接近的，可与新点形成新的凸包的点，把中间点删掉，更新\(lp,rp\)即可
具体实现：code
cdq分治
题目
P4027 [NOI2007] 货币兑换
\(p.s.\) 这题卡精度卡飞了（数据最小\(10^{-17}\)），\(eps\)要设成\(10^{-18}\)
标签：10,rp,凸包,Splay,斜率,lp,动态,优化 From： https://www.cnblogs.com/zhone-lb/p/18539305