dwjshift's Blog

实现水平序动态凸包的小技巧

| Comments

纠结了半天之后还是决定写水平序……
总觉得极角序精度各种不靠谱(雾
不过水平序比较麻烦的一点是要维护上下两个凸壳
在网上搜了一下似乎大家都是各种xor?感觉不是很优美啊……
后来自己就yy了个方法,维护上凸壳的时候,把横纵坐标都取负,然后就变成维护两个下凸壳啦!(鼓掌熊

附上bzoj1249(SGU277)代码

code

#include <cstdio>
#include <set>
#include <cctype>
#define repu(i,x,y) for (i=x; i<=y; ++i)
using namespace std;
 
typedef long long LL;
int n,i;
LL ans;
char ch;
struct point
{
    LL x,y;
    inline bool operator<(const point &t) const
    {
        return x<t.x || x==t.x && y<t.y;
    }
    bool operator==(point t)
    {
        return x==t.x && y==t.y;
    }
    point operator-(point t) const
    {
        point ret;
        ret.x=x-t.x,ret.y=y-t.y;
        return ret;
    }
    void read();
    void rev()
    {
        x=-x,y=-y;
    }
} x,y,z;
set<point> bst[2];
set<point>::iterator l,r,t;
 
inline int getLL()
{
    bool flag=0;
    while (!isdigit(ch=getchar()) && ch!='-');
    if (ch=='-')
        flag=1,ch=getchar();
    LL x=ch-'0';
    for (; isdigit(ch=getchar()); x=x*10+ch-'0');
    return flag?-x:x;
}
 
void point::read()
{
    x=getLL(),y=getLL();
}
 
LL cross(point a,point b)
{
    return a.x*b.y-b.x*a.y;
}
 
void erase_l()
{
    while (l!=bst[i].begin() && cross(*--(t=l)-*l,x-*l)>=0)
        ans-=cross(*t,*l),bst[i].erase(l),l=t;
}
 
void erase_r()
{
    while (++(t=r)!=bst[i].end() && cross(x-*r,*t-*r)>=0)
        ans-=cross(*r,*t),bst[i].erase(r),r=t;
}
 
void insert()
{
    repu(i,0,1)
    {
        if (i)
            x.rev();
        if ((r=bst[i].lower_bound(x))==bst[i].end())
        {
            --(l=r),erase_l(),bst[i].insert(x),ans+=cross(*l,x);
            continue;
        }
        if (x==*r)
            return;
        if (r!=bst[i].begin())
        {
            if (cross(*--(l=r)-x,*r-x)>=0)
                continue;
            ans-=cross(*l,*r),erase_l(),ans+=cross(*l,x);
        }
        erase_r(),ans+=cross(x,*r),bst[i].insert(x);
    }
}
 
int main()
{
    x.read(),y.read(),z.read(),scanf("%d",&n);
    bst[0].insert(y),bst[0].insert(z);
    y.rev(),z.rev();
    bst[1].insert(y),bst[1].insert(z);
    insert();
    while (n--)
        x.read(),insert(),printf("%lld\n",ans);
    return 0;
}

Comments

comments powered by Disqus