凸包练习
本文主要是对遇到的进阶凸包问题进行总结
1. JOISC 2012 Day2 T2「星座」
直接看，完全没思路，看题解，三角剖分什么鬼，于是建议去CF1045E先看看类似题解
干脆单独写一篇博客吧
2. atcoder Holes
这个东西，我觉得有必要写以下两点
-
最好最好不要手动特判输出，容易错（0.5，0.5）情况
-
使用反函数得到角度后，例如求得$ acos$ 后不要$/180$这样，要$/acos(-1)$
-
精度问题：不管是double还是long double，都只能管到16位
3. 动态凸包
其实就是多维护了一个set罢了。
4.合金
这道题就是要求在凸包上选择几个点，这几个点构成的几何图形正好能囊括另外m个点，求最少的点数。
对于凸包上任意一个有向边而言，我们规定，这条边可以被选择当且仅当这m个点在这条有向边的左侧。
然后$ floyd$ 最短路上，将合法的边长度定为1，找一个最小环即可。
注意点是：
- 这个环应该是个有向环，所以不能仅仅凭靠一个有向边连上一个无向边。
- 当这个点在某一个有向线段上(叉积为0)，注意判断$dis$的大小，即这个点虽然在直线上但不在线段上。