Hobo Chen

ACM-2D计算几何(TBD)

这篇博客包含了一些常见2D计算几何算法。

一直感觉计算几何是个0/100的东西,以及通常在ACM中属于中后期题目;所以一直拖着没有写这个大类。

但计算几何的题目我还是挺喜欢的(划掉)。

这篇博客中所涉及的模板/题目代码可以在这个仓库中找到。

基础

  • 点类,精度控制
  • 点积,叉积
  • 点在多边形内判定
  • 直线/线段的相交判定,求交点
  • 直线与圆的交点
  • 三角形四心,费马点
  • 最近点对
  • 凸包
  • 半平面交
  • 旋转卡壳

最近点对

HDU1007

最近点对,100000个点。

半平面交

HDU3761

进阶

  • 凸包进阶
    • 稳定凸包(POJ1228)
    • 最大空凸包()
    • 判断点在凸包内
    • 凸包面积并(CF#83 Div1 E)
    • 两个凸包的最近距离()
    • 完全动态凸包()
  • 格点数问题
  • 圆进阶
    • 圆与圆的交点
    • 圆与圆的面积并
    • 圆与多边形的交
    • 最小圆覆盖
  • 矩形面积/周长的交/并
  • 多边形的费马点

矩形面积并

HDU1542

数据量特别小,n2的暴力也可以通过。

这里的代码是离散化+线段树的做法。

圆进阶

最小圆覆盖

BZOJ2823