CVBB ACM Team

这是本文档旧的修订版！

---

• Pick 定理：给定顶点坐标均是整点（或正方形格子点）的简单多边形，皮克定理说明了其面积 A 和内部格点数目 i 、边上格点数目b 的关系 A=i+b/2-1
• 接上：如果三角形格点就只把右边乘2
• 线段覆盖整点数:gcd(dx,dy)+1，记得去重

把cls的几何wiki搬来一部分：

一个不错的网站 http://judge.u-aizu.ac.jp/onlinejudge/finder.jsp?course=CGL

一个不错的模板 https://pan.baidu.com/share/link?shareid=160419&uk=3104636224&errno=0&errmsg=Auth%20Login%20Sucess&&bduss=&ssnerror=0

CAUTION：在判断det或者dot之后的sign的时候EPS一定要注意，对精度问题要保持敏感。

几何板子： https://ideone.com/78otaL

快速凸包操作板子：http://ideone.com/cqUxSF