AOAPC I: Volume 1.Maths-Simple Geometry

Written by    19:20 December 10, 2014 

<<算法竞赛入门经典>> UVaoj第二卷计算几何习题:

10250-The Other Two Trees

第一次做到WF的题目(*ノωノ), 只不过是道热身题…

这道题BB那么多其实就是给出一个菱形的一个对角两个点, 要求出另外一对角的坐标, 但是是可以多选的, 也就是说你求出任意两个点, 只要能跟作为一对角点与给出的两个点组成菱形即可, 因为是任意, 直接当作正方形即可.

579-Clock Hands

水题, 注意角度只能是正的并且不能大于180度.

375-Inscribed Circles and Isosceles Triangles

实在有点想不通这道题的AC率怎么这么低, 看不出来难在哪里, 读懂题意注意是一层一层的内切圆套公式推出公式求就是了.

10387-Billiard

感觉相对于来说是这一卷水题里面最难的题目, 但是不知道为什么AC率是最高的, 因为是水题所以AC率没有任何参考价值么?

话说回来高中几何都忘的差不多了( TДT), 注意台球的轨迹之间要么相交要么平行, 然后各种镜像加平移最后用勾股定理求出路程.

10112-Myacm Traingles

一开始用这篇blog中的方法来判断点是否在三角形内, 估计是float的等于没处理好, 最后还是用题目中的公式+面积法来判断的, 注意那个0.5可以毫不犹豫地丢掉, 这样就只有整数运算了, 不然可能会WA.

总算是把Chapter 5 Over了, 最后一卷的题目尤其水, 却还是磨磨蹭蹭三四天, 总的来说算是这五六十道题目下来也算是入门了一丁点, 接下来得提高效率, 争取在一个月以内把剩下的全部撸完吧!

Category : acm

Tags :