极其BT的东西，又卡精度又卡边界情况，代码还异常长（依托答辩）。
解决问题
给出一堆线段或直线（\(log^2\) 或 \(log\) 复杂度），问某个 \(x\) 坐标上最高的线。可以搭配 \(DP\) 进行转移上的优化，常见模型为 \(n^2\) 的 \(f_u=min(a_u\times a_v+f_v)\) 样子。
原理
以 \(x\) 坐标建立线段树（可以离散化）。维护一段区间内的优势线段（在 \(mid\) 处最高的一条线）。
- 插入
找到全覆盖区间，每个区间向交点下放，没有交点则不下放。
- 查询
所有包含 \(x\) 的 \(log\) 层都取一个 \(max\)。
虽然思想比较好理解，但是代码是真的烦。
-
离散化
-
特判竖线
-
浮点误差
-
相交找交点改为比较左右高度
-
对于
a[0]的处理（\(INF\)） -
对于DP初值（\(f_0\)），应当考虑是否放到线段树里
-
有时可以维护极值，加上
pushup、树剖。 -
pushup只能有儿子时进行，同时，原本的最值应当参与到儿子节点取最值更新的过程中（类似：tr[u].mn=min(tr[u].mn,min(tr[ls].mn,tr[rs].mn))），题目。
扔一个板子
const double eps=1e-10;
namespace lc_seg{
int tot;
struct xian{
double k,b;
}a[M];
struct node{
int l,r,best;
double mly,mry;
}tr[N<<2];
inline int cmp(double x,double y){
return x-y>eps?1:(y-x>eps?-1:0);
}
inline double gety(int i,ll x){
return a[i].k*x+a[i].b;
}
inline void build(int u,int l,int r){
tr[u]=/**/{l,r,0,0,0};
if(l==r) return ;
int mid=l+r>>1;
build(u<<1,l,mid),build(u<<1|1,mid+1,r);
}
inline void mdf(int u,int l,int r,int x){
int mid=tr[u].l+tr[u].r>>1;
if(l<=tr[u].l&&tr[u].r<=r){
int &k=tr[u].best;
double ly=gety(x,tr[u].l),ry=gety(x,tr[u].r);
if(!k||(cmp(ly,tr[u].mly)==1&&cmp(ry,tr[u].mry)==1)){
k=x;
tr[u].mly=ly,tr[u].mry=ry;
}
else if(cmp(ly,tr[u].mly)==1||cmp(ry,tr[u].mry)==1){
if(cmp(gety(x,mid),gety(k,mid))==1){
swap(k,x);
tr[u].mly=ly,tr[u].mry=ry;
}
if(cmp(ly,tr[u].mly)==1) mdf(u<<1,l,r,x);
else mdf(u<<1|1,l,r,x);
}
return ;
}
if(l<=mid) mdf(u<<1,l,r,x);
if(r>mid) mdf(u<<1|1,l,r,x);
}
inline double query(int u,int x){
if(tr[u].l==tr[u].r) return tr[u].mly;
int mid=tr[u].l+tr[u].r>>1;
double res=gety(tr[u].best,x);
if(x<=mid) res=max(query(u<<1,x),res);
else res=max(query(u<<1|1,x),res);
return res;
}
inline void add_line(ll ax,ll ay,ll bx,ll by){
if(ax>bx) swap(ax,bx),swap(ay,by);
++tot;
if(ax==bx) a[tot]=/**/{0,1.0*max(ay,by)};
else{
double k=1.0*(by-ay)/(bx-ax);
a[tot]=/**/{k,1.0*ay-k*ax};
}
mdf(1,ax,bx,tot);
}
}