网页资讯视频图片知道文库贴吧地图采购
进入贴吧全吧搜索
noip吧 关注：25,164贴子：642,102
  • 16回复贴，共1页

【蒟蒻求助】 怎么动态维护凸包呀

用splay维护一个极角区间，每插入一个点就找到该点的极角区间然后往两边扫一下是否可以更新，更新用叉积判是不是凸的
二维的
可不可以呀？


可是可以，但是我建议分别维护上下凸壳。。。当然，只是因为我只会这么写


∠看不懂


顺便问一个求凸包的时候的问题
当前点p[i],栈顶两个元素p[st[top]],p[st[top-1]]
是应该判
while (det(p[st[top]]-p[st[top-1]],p[i]-p[st[top-1]])>0) --top;
还是
while (det(p[st[top-1]]-p[st[top]],p[i]-p[st[top]])>0) --top;
@法法塔
你是怎么写的？


@凌云七风


用atan2排极角序在坐标接近1e+7却只有个位数有差别的情况下会不会跪精度？
T_T


atan2精度还是够看啦…据使用者说结果的精度能到1e-8左右…


可以不用角度


扫二维码下载贴吧客户端

下载贴吧APP
看高清直播、视频！
  • 16回复贴，共1页
分享到: