计算几何 - 从入门到跳楼
题单介绍
# 0XFF 前言
计算几何题单,从入门题到黑题全难度,祝你~~被虐~~学习愉快!
本题单还包括一些外 oj 的经典题目,无法在题单【题目列表】中给出,仅在下方列出。
本题单的题目按照算法类别排序,在算法的基础上按照难度高低排序。
# 0X00 计算几何基础
这些是特别基础的计算几何,有些是推式子,有些是找规律,适合新手入门。
- P1652 圆
- P2181 对角线
- P1257 平面上的最接近点对
- P1142 轰炸
- P2180 摆石子
- P1355 神秘大三角
- P1325 雷达安装
# 0X01 凸包
- P2742 [USACO5.1]圈奶牛Fencing the Cows /【模板】二维凸包
- P3194 [HNOI2008]水平可见直线
- P6247 [SDOI2012]最近最远点对
- UVA11626 Convex Hull
- P3299 [SDOI2013]保护出题人
- P2924 [USACO08DEC]Largest Fence G
- P3122 [USACO15FEB]Fencing the Herd G
- UVA1303 Wall
- P3829 [SHOI2012]信用卡凸包
- UVA681 Convex Hull Finding
- UVA675 Convex Hull of the Polygon
- P4724 【模板】三维凸包
# 0X02 旋转卡壳
- P1452 [USACO03FALL]Beauty Contest G /【模板】旋转卡壳
- P3187 [HNOI2007]最小矩形覆盖
- UVA10173 Smallest Bounding Rectangle
# 0X03 半平面交
- P4196 [CQOI2006]凸多边形 /【模板】半平面交
- P3222 [HNOI2012]射箭
- P3493 [POI2009]WSP-Island
- P3297 [SDOI2013]逃考
- [POJ2451 Uyuw's Concert](http://poj.org/problem?id=2451)
- [POJ1279 Art Gallery](http://poj.org/problem?id=1279)
# 0X04 杂题
- P1742 最小圆覆盖