srgba哥越来越重口了。
自从数据结构专场之后又出了一套几何专场。。我了个去。
目前本菜ac的只有前三题。。
| A | Smallest Regular Polygon |
推个公式，本质就是拆分成n个小三角形的面积，n为偶时显然；n为奇时，长边对中心的角为(2pi/n)*floor(n/2)，易得中心到顶点的距离。
就是初中时候的平面几何。可惜纯手推推不出公式来，无奈用了正弦＋余弦定理。无解是指内角和不为180，多解是骗人的。
三点确定一个圆是大水题。
| D | Composite Transformations
|
三维的仿射变换，还没写，好麻烦的。
终于搞定了。时隔一个月。
http://www.cppblog.com/aswmtjdsj/archive/2011/11/04/159593.html
| F | Polishing a Extruded Polygon |
金属铸造属于线性规划问题。－－某《计算几何》书言
- -sketchup是个好软件啊。自己写就蛋疼了- -这尼玛模拟也太难了吧。
| H | Smallest Enclosing Rectangle |
最小面积／周长包围矩形是旋转卡壳。
最小包围长方体？？？这是神马？！（三维旋转卡壳？？？）
| J | A Strange Opera House II |
光线反射，又一个坑爹题。（邓老师的书上有伪代码的样子。。）
平面点定位，邓老师的书：梯形剖分。
| L | All-Pair Farthest Points |
卡了好久，旋转卡壳处理共线点的时候会有各种bug，尤其这题还给了一个凸包。。。正解到底是神马？voronoi图？（据说三分可过）
| M | Bounding Volume Hierarchy |
这题太nb了。。。。。空间子区域划分。。。。。八叉树神马？！？
lrj坑爹题。。。
机器人运动路径规划。。。脑中瞬间浮现了四个字“随意所之”。
感觉乳鸽就是把那本计算几何书上的算法出了一遍。。全身心坑爹。。。
.