Posts match “ 计算几何 ” tag:

http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=533&page=show_problem&problem=2109

  1. 选择在凸包上的直线更好
  2. 如何算距离?观察到(对于某一条直线,由于所有点都在直线一侧,所以所有的符号相同),所以预处理后可以求之。
继续阅读

http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=4064

思路:微延长每条线段,这样检测区域的封闭性就可以看各个端点之间能否直接相连,最后看原点(怪物位置)能否dfs达到一个坐标很大的点。
注意:若延长后的端点在任意一条线段上则忽略该点。(因为微延长的技巧是为了造成“墙”的效果,且“墙”中间是不能有点的)

继续阅读

设三顶点的坐标为:,且

内心:
设内心为,则有
所以

证明见http://wenku.baidu.com/link?url=6h-UkNenDf1Kd9fP1VU6z1gcN7Jwbnm3N9udRqVNKklw2Wxamb2s3cyo0Wu2EcW7z8s8nQNp1ksiv7UWK4_GcdQuYNb1-A154tqFluUbPUW

外心:
因为过三点圆的方程为
故三角形外心坐标为
或者求中垂线交点也行。

垂心:
公式:http://zhidao.baidu.com/link?url=1ZvfqhyGY56YGbxUZtZJsardCqp7zeHi-J0SH-mQ8E0l7PaPaWAaJZxbmz26W5EP-76aHWIiFaXL9VMP6pPfZ_
还是直接当计算几何做算了。。

旁心:



记忆方法:
-++
+-+
++-
另:三角形关于顶点A、B、C的旁切圆的半径分别是

重心就不用说了。