「学习笔记」计算几何杂论

向量

坐标表示 ((x,y))
叉乘：((n,m)) 和 ((x,y)) 的向量叉积的结果为 (ny-mx)，利用这种方法可以判断两个向量的方向

也就是如果 mul(Vector x,Vector y)>=0 那么 (x) 在 (y) 的逆时针

如果为负也就是在顺时针，有一个小口诀：顺负逆正

这里注意：叉积可能会爆 int

凸包

概念：「HAOI2011」防线修建

根据题目的图示，可以得到如果一个上凸壳两点间的斜率是单调递减的

类似的，下凸壳是斜率递增的

那么这题目离线之后用 (set) 维护凸包周长即可

凸包与斜率优化：

(dp) 式子的转移的经典优化有斜率优化，单调队列处理的斜率优化条件比较苛刻，需要两边都满足单调

本题中并不满足 (l_i) 有任何单调性，那么考虑动态维护一个凸包

这类题目有很多种解法，也就引出了多种维护凸包的方式：

「NOI2014」购票

用线段树来维护凸包

对于线段树上的每个区间维护区间里面的点的凸壳，每次对 (log) 个节点插入

考虑到每个节点每个点只会入队和出队一次，那么复杂度是 (1) 个 (log)

但是在这个题目中考虑转移顺序的问题，要先处理 (out) 序，每个点先查得到答案之后在 (out[x]) 处加入新点
「BZOJ2402」陶陶的难题

(0/1) 分数规划转化问题之后得到维护 (y-mid imes x+q-mid imes p) 的式子

因为分别独立，那么把 (x,y) 和 (p,q) 分开扔到两个线段树里面

同时需要树链剖分，那么复杂度达到惊人的 (log ^4)

其实没啥，因为后面三个根本跑不满，线段树无法满 (log) ，vector里面的二分也是不行的，重链剖分更是小常数
「SDOI2014」向量集

首先由点乘的公式能得到斜率优化的式子，这是 (trivial) 的

那么套上线段树维护凸包就行了

不过这题目中答案的来源不仅是 ((x,y)) 来构成，也可以是一个下凸壳

那么对于每个加入向量集里面的点维护 ((x,y)) 和 ((-x,-y)) 即可

同时对于每个线段树上的点，(vector) 的大小等于区间大小再按照 (x) 归并

记得要清空……

「NOI2009」货币兑换

平衡树维护凸包或者 (cdq) 分治来维护

平衡树维护就是考虑凸包的性质，每次需要修改前趋和后继，对应上去就是 (pre,nxt)

对于具体实现而言，维护 (l[x],r[x]) 表示当前点左边和右边的斜率，删点的时候细节比较多

inline int find(int x,double num) 
{
    if(!x) return 0;
    if(l[x]+eps>=num&&r[x]<=num+eps) return x;
    if(l[x]<num+eps) return find(ls[x],num);
    return find(rs[x],num);    
}  
inline double calc(int p,int q)
{
    if(fabs(x[p]-x[q])<eps) return -inf;
    return (y[p]-y[q])/(x[p]-x[q]);
}
inline int pre(int x)
{
    int now=ls[x],res=now; 
    while(now)
    {
        if(l[now]+eps>=calc(now,x)) res=now,now=rs[now];
        else now=ls[now];
    } return res;
}
inline int nxt(int x) 
{   
    int now=rs[x],res=now;
    while(now) 
    {
        if(r[now]<=eps+calc(now,x)) res=now,now=ls[now];
        else now=rs[now]; 
    } return res;
}
inline void del(int x)
{
    rt=ls[x]; fa[rt]=0; fa[rs[x]]=rt; rs[rt]=rs[x]; 
    r[rt]=l[rs[x]]=calc(rt,rs[x]);
    return ; 
}
inline void work(int x)
{
    splay(x,0);
    if(ls[x])
    {
        int p=pre(x); splay(p,x); rs[p]=0;
        r[ls[x]]=l[x]=calc(ls[x],x);
    }else l[x]=inf;
    if(rs[x])
    {
        int tmp=nxt(x); splay(tmp,x); ls[tmp]=0;
        l[rs[x]]=r[x]=calc(rs[x],x);
    }else r[x]=-inf;
    if(l[x]<=eps+r[x]) del(x);
    return ;
}
inline void insert(int &now,int fat,int id)
{
    if(!now){now=id; fa[now]=fat; return ;}
    if(x[id]<=x[now]+eps) insert(ls[now],now,id); else insert(rs[now],now,id);
    return ;
}

(cdq) 分治就是一个经典的左中右转移

对于当前分治区间 ([l,r])，先处理左边的贡献，把左边按照 (dp) 建立凸包，再做右边

代码没有写，因为这种题貌似是没少做

复杂度貌似并不比上面的做法多 (log)，但是不能在线

应用

其实有些题目就是转化出来是凸包的模型，然后用二分斜率的方式处理

Luogu4192 旅行规划

区间问题考虑初等数据结构，发现线段树并不能维护之后考虑分块

那么可以给每个块建一个凸包，(i-st+1) 是横坐标，(sum_i) 是纵坐标

对于修改操作，小块重构，大块加等差数列，打标记维护公差和首项

注意在 (r) 以后的点的 (sum) 应该增加 (len imes (r-l+1))

查询操作，小块暴力修改并且重构，大块对着 (-d) 二分就行

上面提到的凸包二分是比较恶心的东西，不好写对：

一种可行的写法是

l=0,r=st[id].size()-2;
while(l<=r) check->slope r=mid-1; else l=mid+1;
ans=l;

这个对于上下凸壳需要改一些条件

做的题目并不够多，所以本文会持续更新

「学习笔记」计算几何杂论

向量

凸包

概念： 「HAOI2011」防线修建

凸包与斜率优化：

应用

概念：「HAOI2011」防线修建