做平面那个网站素材好,深圳市龙华区,服务外包企业有哪些,石排网站设计http://www.cnblogs.com/eric-blog/archive/2011/05/31/2064785.html http://hi.baidu.com/novosbirsk/blog/item/723a9727a9ab8804918f9dca.html其实也谈不上推荐#xff0c;只是自己做过的题目而已#xff0c;甚至有的题目尚未AC#xff0c;让在挣扎中。之所以推荐计算几何… http://www.cnblogs.com/eric-blog/archive/2011/05/31/2064785.html http://hi.baidu.com/novosbirsk/blog/item/723a9727a9ab8804918f9dca.html其实也谈不上推荐只是自己做过的题目而已甚至有的题目尚未AC让在挣扎中。之所以推荐计算几何题是因为本人感觉ACM各种算法中计算几何算是比 较实际的算法在很多领域有着重要的用途例如本人的专业GIS。以后若有机会我会补充、完善这个列表。计算几何题的特点与做题要领1.大部分不会很难少部分题目思路很巧妙2.做计算几何题目模板很重要模板必须高度可靠。3.要注意代码的组织因为计算几何的题目很容易上两百行代码里面大部分是模板。如果代码一片混乱那么会严重影响做题正确率。4.注意精度控制。5.能用整数的地方尽量用整数要想到扩大数据的方法扩大一倍或扩大sqrt2。因为整数不用考虑浮点误差而且运算比浮点快。一。点线面形基本关系点积叉积的理解POJ 2318 TOYS推荐http://acm.pku.edu.cn/JudgeOnline/problem?id2318POJ 2398 Toy Storage推荐http://acm.pku.edu.cn/JudgeOnline/problem?id2398一个矩形有被若干直线分成N个格子给出一个点的坐标问你该点位于哪个点中。知识点其实就是点在凸四边形内的判断若利用叉积的性质可以二分求解。POJ 3304 Segmentshttp://acm.pku.edu.cn/JudgeOnline/problem?id3304知识点线段与直线相交注意枚举时重合点的处理POJ 1269 Intersecting Lines http://acm.pku.edu.cn/JudgeOnline/problem?id1269知识点直线相交判断求相交交点POJ 1556 The Doors 推荐http://acm.pku.edu.cn/JudgeOnline/problem?id1556知识点简单图论简单计算几何先求线段相交然后再用Dij求最短路。POJ 2653 Pick-up sticks http://acm.pku.edu.cn/JudgeOnline/problem?id2653知识点还是线段相交判断POJ 1066 Treasure Hunt http://acm.pku.edu.cn/JudgeOnline/problem?id1066知识点线段相交判断不过必须先理解“走最少的门”是怎么一回事。POJ 1410 Intersection http://acm.pku.edu.cn/JudgeOnline/problem?id1410知识点线段与矩形相交。正确理解题意中相交的定义。详见http://hi.baidu.com/novosbirsk/blog/item/68c682c67e8d1f1d9d163df0.htmlPOJ 1696 Space Ant 推荐http://acm.pku.edu.cn/JudgeOnline/problem?id1696德黑兰赛区的好题目。需要理解点积叉积的性质POJ 3347 Kadj Squares http://acm.pku.edu.cn/JudgeOnline/problem?id3347本人的方法极度猥琐。复杂的线段相交问题。这个题目是计算几何的扩大数据运算的典型应用扩大根号2倍之后就避免了小数。POJ 2826 An Easy Problem?! 推荐http://acm.pku.edu.cn/JudgeOnline/problem?id2826问两条直线组成一个图形能容纳多少雨水。很不简单的Easy Problem要考虑所有情况。你不看discuss看看能否AC。本人基本不能提示一下水是从天空垂直落下的。POJ 1039 Pipe http://acm.pku.edu.cn/JudgeOnline/problem?id1039又是线段与直线相交的判断再加上枚举的思想即可。POJ 3449 Geometric Shapes http://acm.pku.edu.cn/JudgeOnline/problem?id3449判断几何体是否相交不过输入输出很恶心。此外还有一个知识点就是给出一个正方形边不与轴平行的两个对角线上的顶点需要你求出另外两个点。必须掌握其方法。POJ 1584 A Round Peg in a Ground Hole http://acm.pku.edu.cn/JudgeOnline/problem?id1584知识点点到直线距离圆与多边形相交多边形是否为凸POJ 2074 Line of Sight 推荐http://acm.pku.edu.cn/JudgeOnline/problem?id2074与视线问题的解法关键是求过两点的直线方程以及直线与线段的交点。数据有一个trick要小心。二。凸包问题POJ 1113 Wall http://acm.pku.edu.cn/JudgeOnline/problem?id1113知识点赤裸裸的凸包问题凸包周长加上圆周。POJ 2007 Scrambled Polygon http://acm.pku.edu.cn/JudgeOnline/problem?id2007知识点凸包按极角序输出方案POJ 1873 The Fortified Forest 推荐http://acm.pku.edu.cn/JudgeOnline/problem?id1873World Final的水题先求凸包然后再搜索。由于规模不大可以使用位运算枚举。详见http://hi.baidu.com/novosbirsk/blog/item/333abd54c7f22c52574e0067.htmlPOJ 1228 Grandpas Estate 推荐http://acm.pku.edu.cn/JudgeOnline/problem?id1228求凸包顶点数目很多人求凸包的模板是会多出点的虽然求面积时能得到正确答案但是在这个题目就会出问题。此外还要正确理解凸包的性质。POJ 3348 Cows http://acm.pku.edu.cn/JudgeOnline/problem?id3348凸包面积计算三。面积问题公式问题POJ 1654 Area http://acm.pku.edu.cn/JudgeOnline/problem?id1654知识点利用有向面积叉积计算多边形面积POJ 1265 Area http://acm.pku.edu.cn/JudgeOnline/problem?id1265POJ 2954 Triangle http://acm.pku.edu.cn/JudgeOnline/problem?id2954Pick公式的应用多边形与整点的关系。存在一个GCD的关系四。半平面交半平面交的主要应用是判断多边形是否存在核还可以解决一些与线性方程组可行区域相关的问题就是高中时的那些。POJ 3335 Rotating Scoreboardhttp://acm.pku.edu.cn/JudgeOnline/problem?id3335POJ 3130 How I Mathematician Wonder What You Are! http://acm.pku.edu.cn/JudgeOnline/problem?id3130POJ 1474 Video Surveillancehttp://acm.pku.edu.cn/JudgeOnline/problem?id1474知识点半平面交求多边形的核存在性判断POJ 1279 Art Gallery http://acm.pku.edu.cn/JudgeOnline/problem?id1279半平面交求多边形的核求核的面积POJ 3525 Most Distant Point from the Sea 推荐http://acm.pku.edu.cn/JudgeOnline/problem?id3525给出一个多边形求里面的一个点其距离离多边形的边界最远也就是多边形中最大半径圆。可以使用半平面交二分法解。二分这个距离边向内逼近直到达到精度。POJ 3384 Feng Shui 推荐http://acm.pku.edu.cn/JudgeOnline/problem?id3384半平面交实际应用用两个圆覆盖一个多边形问最多能覆盖多边形的面积。解法用半平面交将多边形的每条边一起向“内”推进R得到新的多边形然后求多边形的最远两点。POJ 1755 Triathlon 推荐http://acm.pku.edu.cn/JudgeOnline/problem?id1755半平面交判断不等式是否有解。注意不等式在转化时正负号的选择这直接影响到半平面交的方向。POJ 2540 Hotter Colder http://acm.pku.edu.cn/JudgeOnline/problem?id2540半平面交求线性规划可行区域的面积。POJ 2451 Uyuws Concerthttp://acm.pku.edu.cn/JudgeOnline/problem?id2451Zzy专为他那篇nlogn算法解决半平面交问题的论文而出的题目。五。计算几何背景实际上解题的关键是其他问题数据结构、组合数学或者是枚举思想若干道经典的离散化扫描线的题目ACM选手必做题目POJ 1151 Atlantis 推荐http://acm.pku.edu.cn/JudgeOnline/problem?id1151POJ 1389 Area of Simple Polygonshttp://acm.pku.edu.cn/JudgeOnline/problem?id1389矩形离散化线段树处理矩形面积求交POJ 1177 Picture 推荐http://acm.pku.edu.cn/JudgeOnline/problem?id1177矩形离散化线段树处理矩形交的周长这个题目的数据比较强。线段树必须高效。 POJ 3565 Ants 推荐http://acm.pku.edu.cn/JudgeOnline/problem?id3565计算几何中的调整思想有点像排序。要用到线段相交的判断。详见http://hi.baidu.com/novosbirsk/blog/item/fb668cf0f362bec47931aae2.htmlPOJ 3695 Rectangles http://acm.pku.edu.cn/JudgeOnline/problem?id3695又是矩形交的面积但是由于是多次查询而且矩形不多使用组合数学中的容斥原理解决之最适合。线段树是通法但是除了线段树还有其他可行的方法。POJ 2002 Squares http://acm.pku.edu.cn/JudgeOnline/problem?id2002枚举思想求平面上若干个点最多能组成多少个正方形点的HashPOJ 1434 Fill the Cisterns!推荐http://acm.pku.edu.cn/JudgeOnline/problem?id1434一开始发昏了准备弄个线段树。其实只是个简单的二分。六。随机算法POJ 2420 A Star not a Tree? http://acm.pku.edu.cn/JudgeOnline/problem?id2420多边形的费马点。所谓费马点就是多边形中一个点P该点到其他点的距离之和最短。四边形以上的多边形没有公式求费马点因此可以使用随机化变步长贪心 法。详见http://hi.baidu.com/novosbirsk/blog/item/75983f138499f825dd54019b.html七。解析几何这种题目本人不擅长所以做得不多模板很重要。当然熟练运用叉积、点积的性质还是很有用的。POJ 1375 Intervals http://acm.pku.edu.cn/JudgeOnline/problem?id1375知识点过圆外一点求与圆的切线POJ 1329 Circle Through Three Points http://acm.pku.edu.cn/JudgeOnline/problem?id1329求三角形外接圆POJ 2354 Titanichttp://acm.pku.edu.cn/JudgeOnline/problem?id2354求球面上两个点的距离而且给的是地理经纬坐标。POJ 1106 Transmittershttp://acm.pku.edu.cn/JudgeOnline/problem?id1106角度排序知道斜率求角度使用atan函数。POJ 1673 EXOCENTER OF A TRIANGLEhttp://acm.pku.edu.cn/JudgeOnline/problem?id1673可以转化为三角形的垂心问题。八。旋转卡壳POJ 2187 Beauty Contest http://acm.pku.edu.cn/JudgeOnline/problem?id2187凸包求最远点对。可以暴力枚举也可以使用旋转卡壳。POJ 3608 Bridge Across Islands难http://acm.pku.edu.cn/JudgeOnline/problem?id3608两个凸包的最近距离。本人的卡壳始终WA。郁闷。九。其他问题POJ 1981 Circle and Points http://acm.pku.edu.cn/JudgeOnline/problem?id1981求单位圆最多能覆盖平面上多少个点 转载于:https://www.cnblogs.com/waytofall/archive/2012/09/03/2669703.html
