凸包练习

凸包练习

本文主要是对遇到的进阶凸包问题进行总结

• 凸包练习
  • 1. JOISC 2012 Day2 T2「星座」
  • 2. atcoder Holes
  • 3. 动态凸包
  • 4.合金

1. JOISC 2012 Day2 T2「星座」

直接看，完全没思路，看题解，三角剖分什么鬼，于是建议去CF1045E先看看类似题解

干脆单独写一篇博客吧

2. atcoder Holes

这个东西，我觉得有必要写以下两点

1. 最好最好不要手动特判输出，容易错（0.5，0.5）情况

2. 使用反函数得到角度后，例如求得$ acos$ 后不要$/180$这样，要$/acos(-1)$

3. 精度问题：不管是double还是long double，都只能管到16位

3. 动态凸包

其实就是多维护了一个set罢了。

4.合金

这道题就是要求在凸包上选择几个点，这几个点构成的几何图形正好能囊括另外m个点，求最少的点数。

对于凸包上任意一个有向边而言，我们规定，这条边可以被选择当且仅当这m个点在这条有向边的左侧。

然后$ floyd$ 最短路上，将合法的边长度定为1，找一个最小环即可。

注意点是：

1. 这个环应该是个有向环，所以不能仅仅凭靠一个有向边连上一个无向边。
2. 当这个点在某一个有向线段上(叉积为0)，注意判断$dis$的大小，即这个点虽然在直线上但不在线段上。