萌兽奇缘活动中心

动态凸包

yuanzhiteng

2023-08-12 16:51:02

个人记录

所谓动态凸包，就是时刻会有新的点加入点集中。

这里采用类似 Andrew 的思想分别维护上下凸壳。

当有一个点 i 被加入点集后，分别做以下几步：

判断点是否在上凸壳内。

即是否在上凸壳下方。

由于是对 x 排序，所以可以二分上凸壳中的点，找到第一个 \ge i.x 的点。

将这个点记作 it，前缀点记作 pre，那么只需要判断 (it\to pre)\times(pre\to i) 的叉乘正负性即可判断点 i 是否在上凸壳内。

注意一些边界情况，具体实现见代码。

如果在，后面的有关上凸壳的操作就不用做了。

将点插入上凸壳内并更新上凸壳

先直接插入，然后分别看前面的点和后面的点是否满足凸壳的性质，不满足就删掉。

以前面的点 j 为例，记 pre 为上凸壳中 j 的前缀点，仅需判断叉乘 (pre\to j)\times (j\to i) 的叉乘正负性。

如果 \le 0 说明是往右拐或没拐，直接删掉。

如果 >0 说明是往左拐，不删，后面的点也肯定满足，故直接 return。

后面的点类似处理即可。

判断点是否在下凸壳内。

即是否在下凸壳上方。

与 1 类似，注意叉乘正负性即可。

将点插入下凸壳内并更新下凸壳

与 2 类似，注意叉乘正负性即可。

这样对于任意一个查询 q，均可回答点 q 是否在凸包上了。

使用 map 维护凸包轮廓上点的坐标。

模板题1

#include

typedef long long ll;

#define iter map::iterator

using namespace std;

template

inline void read(T& x){

x = 0; int f = 1; char c = getchar(); while (c < '0' || c > '9') { if (c == '-') f = -f; c = getchar(); }

while (c >= '0' && c <= '9') { x = (x << 3) + (x << 1) + (c ^ 48), c = getchar(); } x *= f;

}

template

inline void read (T &x, Args&... Arg) { read (x), read (Arg...); }

int q;

map up,down; //map维护上下凸壳,first:x,second:y

inline int vec_cmp(ll ax,ll ay,ll bx,ll by,ll cx,ll cy){ //判断向量(a->b),(b->c)叉乘正负性

ll judge = (bx - ax) * (cy - by) - (by - ay) * (cx - bx);

if(judge == 0) return 0;

if(judge > 0) return 1;

return -1;

}

inline bool check_up(ll x,ll y){ //判断(x,y)是否在上凸壳的下方

iter it = up.lower_bound(x);

if(it == up.end()) return 0;

if(it->first == x) return y <= it->second;

if(it == up.begin()) return 0;

iter pre = it;

pre--;

return (vec_cmp(it->first,it->second,pre->first,pre->second,x,y) >= 0);

}

inline bool check_down(ll x,ll y){

iter it = down.lower_bound(x);

if(it == down.end()) return 0;

if(it->first == x) return y >= it->second;

if(it == down.begin()) return 0;

iter pre = it;

pre--;

return (vec_cmp(it->first,it->second,pre->first,pre->second,x,y) <= 0);

}

inline bool delete_up(iter it){ //在上凸壳中删点更新up

if(it == up.begin()) return 0;

iter pre = it,back = it;

pre--;

back++;

if(back == up.end()) return 0;

if(vec_cmp(back->first,back->second,it->first,it->second,pre->first,pre->second) <= 0){

up.erase(it);

return 1;

}

return 0;

}

inline bool delete_down(iter it){ //在下凸壳中删点更新up

if(it == down.begin()) return 0;

iter pre = it,back = it;

pre--;

back++;

if(back == down.end()) return 0;

if(vec_cmp(pre->first,pre->second,it->first,it->second,back->first,back->second) <= 0){

down.erase(it);

return 1;

}

return 0;

}

inline void insert_up(ll x,ll y){ //将(x,y)插入上凸壳中,同时delete_up以更新上凸壳

if(check_up(x,y)) return; //已经在上凸壳内了就不用再加了

up[x] = y;

iter it = up.find(x),j = it; //为了方便之后的操作,统一用iterator操作(find()找的是key(first)所对应的iterator)

if(it != up.begin()){ //往前删点(这样写更方便,不懂可以仔细想想(反复横跳之术))

j--;

while(delete_up(j++)) j--;

}

j++;

if(j != up.end()) //往后删点

while(delete_up(j--)) j++;

}

inline void insert_down(ll x,ll y){ //将(x,y)插入下凸壳中,同时delete_down以更新下凸壳

if(check_down(x,y)) return;

down[x] = y;

iter it = down.find(x),j = it;

if(it != down.begin()){

j--;

while(delete_down(j++)) j--;

}

j++;

if(j != down.end())

while(delete_down(j--)) j++;

}

int main(){

read(q);

int op;

ll x,y;

while(q--){

read(op,x,y);

if(op == 1){ //insert

insert_up(x,y);

insert_down(x,y);

}

else{ //query

if(check_up(x,y) && check_down(x,y)) printf("YES\n");

else printf("NO\n");

}

return 0;

}

此外，如果题目要求维护关于凸包的其它信息，如面积，周长等，均可以在该代码基础上改动去动态维护。

以下将增加某条边的贡献叫做连边，删除某条边的贡献叫做删边。

以维护面积为例，由于面积是由每条边的叉乘贡献的，所以：

每次加点 i 时连两条新增的边，删除原有的一条边。

删点时如对于 pre\to j\to i，仅需删边 pre\to j,j\to i，连边 pre\to i 即可。

思想很容易理解，但是细节特别多。

首先，要注意边界情况。

对于新增点 i 导致的新增边，需要在 check 中增加。

其次，要注意边叉乘的方向性。

比如统一让边为顺时针方向，即上凸壳边 i\to j(x_i

最后，由于 map 无重，所以对于上凸壳和下凸壳两侧连接处的两条边可能没被维护到，所以每次还要将这两条边的贡献加上。

还有各种各样的细节，看代码吧。

模板题2

#include

typedef long long ll;

#define iter map::iterator

using namespace std;

template

inline void read(T& x){

x = 0; int f = 1; char c = getchar(); while (c < '0' || c > '9') { if (c == '-') f = -f; c = getchar(); }

while (c >= '0' && c <= '9') { x = (x << 3) + (x << 1) + (c ^ 48), c = getchar(); } x *= f;

}

template

inline void read (T &x, Args&... Arg) { read (x), read (Arg...); }

int q;

ll ans;

map up,down; //map维护上下凸壳,first:x,second:y

inline int vec_cmp(ll ax,ll ay,ll bx,ll by,ll cx,ll cy){ //判断向量(a->b),(b->c)叉乘正负性

ll judge = (bx - ax) * (cy - by) - (by - ay) * (cx - bx);

if(judge == 0) return 0;

if(judge > 0) return 1;

return -1;

}

inline ll cross(ll ax,ll ay,ll bx,ll by){ //叉乘

return ax * by - ay * bx;

}

inline bool check_up(ll x,ll y){ //判断(x,y)是否在上凸壳的下方

iter it = up.lower_bound(x);

if(it == up.end()) return 0;

if(it->first == x){

if(y <= it->second) return 1;

else{

if(it != up.begin()){

iter pre = it;

pre--;

ans -= cross(it->first,it->second,pre->first,pre->second);

}

iter back = it;

back++;

if(back != up.end()) ans -= cross(back->first,back->second,it->first,it->second);

return 0;

}

if(it == up.begin()) return 0;

iter pre = it;

pre--;

if(vec_cmp(it->first,it->second,pre->first,pre->second,x,y) >= 0)

return 1;

else{

ans -= cross(it->first,it->second,pre->first,pre->second);

return 0;

}

inline bool check_down(ll x,ll y){

iter it = down.lower_bound(x);

if(it == down.end()) return 0;

if(it->first == x){

if(y >= it->second) return 1;

else{

if(it != down.begin()){

iter pre = it;

pre--;

ans -= cross(pre->first,pre->second,it->first,it->second);

}

iter back = it;

back++;

if(back != down.end()) ans -= cross(it->first,it->second,back->first,back->second); //更新边,注意pre->it和it->back都会被断掉

return 0;

}

if(it == down.begin()) return 0;

iter pre = it;

pre--;

if(vec_cmp(it->first,it->second,pre->first,pre->second,x,y) <= 0)

return 1;

else{

ans -= cross(pre->first,pre->second,it->first,it->second); //更新边

return 0;

}

inline bool delete_up(iter it){ //在上凸壳中删点更新up

if(it == up.begin()) return 0;

iter pre = it,back = it;

pre--;

back++;

if(back == up.end()) return 0;

if(vec_cmp(back->first,back->second,it->first,it->second,pre->first,pre->second) <= 0){

ans -= cross(back->first,back->second,it->first,it->second); //更新边,断两条加一条

ans -= cross(it->first,it->second,pre->first,pre->second);

ans += cross(back->first,back->second,pre->first,pre->second);

up.erase(it);

return 1;

}

return 0;

}

inline bool delete_down(iter it){ //在下凸壳中删点更新up

if(it == down.begin()) return 0;

iter pre = it,back = it;

pre--;

back++;

if(back == down.end()) return 0;

if(vec_cmp(pre->first,pre->second,it->first,it->second,back->first,back->second) <= 0){

ans -= cross(pre->first,pre->second,it->first,it->second);

ans -= cross(it->first,it->second,back->first,back->second);

ans += cross(pre->first,pre->second,back->first,back->second);

down.erase(it);

return 1;

}

return 0;

}

inline void insert_up(ll x,ll y){ //将(x,y)插入上凸壳中,同时delete_up以更新上凸壳

if(check_up(x,y)) return; //已经在上凸壳内了就不用再加了

up[x] = y;

iter it = up.find(x),j = it; //为了方便之后的操作,统一用iterator操作(find()找的是key(first)所对应的iterator)

if(it != up.begin()){ //往前删点(这样写更方便,不懂可以仔细想想(反复横跳之术))

j--;

ans += cross(it->first,it->second,j->first,j->second); //加边

while(delete_up(j++)) j--;

}

j++;

if(j != up.end()){ //往后删点

ans += cross(j->first,j->second,it->first,it->second); //加边

while(delete_up(j--)) j++;

}

inline void insert_down(ll x,ll y){ //将(x,y)插入下凸壳中,同时delete_down以更新下凸壳

if(check_down(x,y)) return;

down[x] = y;

iter it = down.find(x),j = it;

if(it != down.begin()){

j--;

ans += cross(j->first,j->second,it->first,it->second);

while(delete_down(j++)) j--;

}

j++;

if(j != down.end()){

ans += cross(it->first,it->second,j->first,j->second);

while(delete_down(j--)) j++;

}

int n;

int main(){

ll x,y;

for(int i=1;i<=3;i++){

read(x,y);

insert_up(x,y);

insert_down(x,y);

}

iter now,back;

read(n);

for(int i=1;i<=n;i++){

read(x,y);

insert_up(x,y);

insert_down(x,y);

ll ret = ans; //ans只维护了上下凸壳边上的贡献,没有维护上下凸壳连接处的贡献,每次重新加上

now = down.end();

now--;

back = up.end();

back--;

ret += cross(now->first,now->second,back->first,back->second);

now = up.begin();

back = down.begin();

ret += cross(now->first,now->second,back->first,back->second);

printf("%lld\n",ret);

}

return 0;

}

散点图怎么用？多维数据分析案例全解读
游戏王VRAINS