专题分享(计算几何&搜索)

分享

例题

按照讲课顺序!

计算几何

• [HAOI2008]下落的圆盘
• [AHOI2012]信号塔
• POJ1113 Wall
• POJ3304 Segment

二维计算几何基础

• [HNOI2007]最小矩形覆盖

旋转卡壳

• [CQOI2006]凸多边形
• [SDOI2013]逃考
• [ZJOI2019]zjoi

半平面交

• [JSOI2018]部落战争|战争
• CF1071E Rain Protection(可当考试题)

Minkowski

其他

• [ZJOI2018]保镖(Pass and delete by [数据删除])

计算几何综合

• [JSOI2004]平衡点/吊打XXX
• [TJOI2010]分金币
• 小木棍[数据加强版]
• [NOI1999]生日蛋糕

其他

考试题目

你猜啊!

• [NOI2005]月下柠檬树
• [COCI2009]Dvapravca
• hdu6158 The Designer(这个要手造数据了...)

大纲

计算几何

• 二维几何基础
• 最小圆覆盖
• 球坐标
• 点在多边形内部判定
• 凸包(Graham与Andrew)
• 半平面交(ZJOI2019zjoi)
• 三角剖分与梯形剖分
• 三维计算几何基础
• 三维凸包
• 闵可夫斯基和

搜索

• $A^*$与$IDA^*$
• 双向BFS
• 剪枝与搜索技巧
• 模拟退火
• 随机增量法
• 乱搞