Tag Archives: 计算几何

//给定n个正方形，所有的线段平行两轴，整点坐标，矩形间不相互重叠或接触 //求从原点能看到多少个矩形

在墙壁林立的场景，你该如何穿过最少的墙壁去获取宝藏？ 枚举，枚举每条边上被分成的几段，看与宝藏形成的线段与几条线段相交即可。

题目简单，一个正 n 变形，求覆盖这个多边形最小的矩形，其边得和 x 轴和 y 轴平行。输入只给出了多边形的 3 个点，根据这 3 个点求出外接圆半径就可以了。这里有解答：http://gisyhy.blog.163.com/blog/static/12939034320107297493479。

计算几何问题，求凸包，然后枚举凸包中的点，不过好像有更简单的办法。 http://www.cppblog.com/varg-vikernes/archive/2010/02/16/107919.aspx

一根棍子夹在两堵墙之间，加热之后会膨胀。求膨胀之后棍子中点距离水平的高度。 勾股定理，二分，已知半径和弧度，如何求弧长？ 假定所求高度为 mid，棍子长度为 len，勾股定理可知圆半径为 (mid * mid + len * len /4)/(2*mid)。

应用平面图的欧拉定理：V + F – E = 2 两两线段求交，得到交点数 V，然后判断每个交点落在几条边上，如果一个点在一条边上，这条边就分裂成两条边，边数加 1。这样得到边数 E。最后直接用欧拉定理解得面数 F。 貌似这样的问题在具体数学中讨论过。 http://baike.baidu.com/view/48903.htm

有 n 棵树(2

给出几根棍子扔出的顺序，问最后哪些棍子不被其他的棍子压住。

题意：有N个点，求这N个点能组成多少个不同的平行四边形。 思路：平行四边形对角形互相平分，所以枚举两个不同的点，求其中点坐标，如果中点坐标相同，说明能组成平行四边形。具体采用哈希查找。 好像曾经见过类似的题目，千万不要枚举 4 个点。