一。点,线,面,形基本关系,点积叉积的理解
POJ 2318 TOYS(推荐)achttp://acm.pku.edu.cn/JudgeOnline/problem?id=2318POJ 2398 Toy Storage(推荐)achttp://acm.pku.edu.cn/JudgeOnline/problem?id=2398 一个矩形,有被若干直线分成N个格子,给出一个点的坐标,问你该点位于哪个点中。 知识点:其实就是点在凸四边形内的判断,若利用叉积的性质,可以二分求解。
POJ 3304 Segmentsachttp://acm.pku.edu.cn/JudgeOnline/problem?id=3304 知识点:线段与直线相交,注意枚举时重合点的处理
POJ 1269 Intersecting Linesachttp://acm.pku.edu.cn/JudgeOnline/problem?id=1269 知识点:直线相交判断,求相交交点
POJ 1556 The Doors (推荐)achttp://acm.pku.edu.cn/JudgeOnline/problem?id=1556 知识点:简单图论+简单计算几何,先求线段相交,然后再用Dij求最短路。
POJ 2653 Pick-up sticks achttp://acm.pku.edu.cn/JudgeOnline/problem?id=2653 知识点:还是线段相交判断
POJ 1066 Treasure Hunthttp://acm.pku.edu.cn/JudgeOnline/problem?id=1066 知识点:线段相交判断,不过必须先理解“走最少的门”是怎么一回事。
POJ 1410 Intersectionachttp://acm.pku.edu.cn/JudgeOnline/problem?id=1410 知识点:线段与矩形相交。正确理解题意中相交的定义。 详见:http://hi.baidu.com/novosbirsk/blog/item/68c682c67e8d1f1d9d163df0.html
POJ 1696 Space Ant (推荐)http://acm.pku.edu.cn/JudgeOnline/problem?id=1696 德黑兰赛区的好题目。需要理解点积叉积的性质
POJ 3347 Kadj Squareshttp://acm.pku.edu.cn/JudgeOnline/problem?id=3347 本人的方法极度猥琐。复杂的线段相交问题。这个题目是计算几何的扩大数据运算的典型应用,扩大根号2倍之后就避免了小数。
POJ 2826 An Easy Problem?!(推荐)http://acm.pku.edu.cn/JudgeOnline/problem?id=2826 问:两条直线组成一个图形,能容纳多少雨水。很不简单的Easy Problem,要考虑所有情况。你不看discuss看看能否AC。(本人基本不能)提示一下,水是从天空垂直落下的。
POJ 1039 Pipehttp://acm.pku.edu.cn/JudgeOnline/problem?id=1039 又是线段与直线相交的判断,再加上枚举的思想即可。
POJ 3449 Geometric Shapeshttp://acm.pku.edu.cn/JudgeOnline/problem?id=3449 判断几何体是否相交,不过输入输出很恶心。 此外,还有一个知识点,就是给出一个正方形(边不与轴平行)的两个对角线上的顶点,需要你求出另外两个点。必须掌握其方法。
POJ 1584 A Round Peg in a Ground Holehttp://acm.pku.edu.cn/JudgeOnline/problem?id=1584 知识点:点到直线距离,圆与多边形相交,多边形是否为凸
POJ 2074 Line of Sight (推荐)http://acm.pku.edu.cn/JudgeOnline/problem?id=2074 与视线问题的解法,关键是求过两点的直线方程,以及直线与线段的交点。数据有一个trick,要小心。
二。凸包问题
POJ 1113 Wall achttp://acm.pku.edu.cn/JudgeOnline/problem?id=1113 知识点:赤裸裸的凸包问题,凸包周长加上圆周。
POJ 2007 Scrambled Polygon achttp://acm.pku.edu.cn/JudgeOnline/problem?id=2007 知识点:凸包,按极角序输出方案
POJ 1873 The Fortified Forest (推荐)http://acm.pku.edu.cn/JudgeOnline/problem?id=1873 World Final的水题,先求凸包,然后再搜索。由于规模不大,可以使用位运算枚举。 详见:http://hi.baidu.com/novosbirsk/blog/item/333abd54c7f22c52574e0067.html
POJ 1228 Grandpa's Estate (推荐) achttp://acm.pku.edu.cn/JudgeOnline/problem?id=1228 求凸包顶点数目,很多人求凸包的模板是会多出点的,虽然求面积时能得到正确答案,但是在这个题目就会出问题。此外,还要正确理解凸包的性质。
POJ 3348 Cows achttp://acm.pku.edu.cn/JudgeOnline/problem?id=3348 凸包面积计算
三。面积问题,公式问题
POJ 1654 Areahttp://acm.pku.edu.cn/JudgeOnline/problem?id=1654 知识点:利用有向面积(叉积)计算多边形面积
POJ 1265 Areahttp://acm.pku.edu.cn/JudgeOnline/problem?id=1265 POJ 2954 Trianglehttp://acm.pku.edu.cn/JudgeOnline/problem?id=2954 Pick公式的应用,多边形与整点的关系。(存在一个GCD的关系)
四。半平面交
半平面交的主要应用是判断多边形是否存在核,还可以解决一些与线性方程组可行区域相关的问题(就是高中时的那些)。
POJ 3335 Rotating Scoreboard achttp://acm.pku.edu.cn/JudgeOnline/problem?id=3335 POJ 3130 How I Mathematician Wonder What You Are! achttp://acm.pku.edu.cn/JudgeOnline/problem?id=3130 POJ 1474 Video Surveillancehttp://acm.pku.edu.cn/JudgeOnline/problem?id=1474 知识点:半平面交求多边形的核,存在性判断
POJ 1279 Art Galleryhttp://acm.pku.edu.cn/JudgeOnline/problem?id=1279 半平面交求多边形的核,求核的面积
POJ 3525 Most Distant Point from the Sea (推荐)achttp://acm.pku.edu.cn/JudgeOnline/problem?id=3525 给出一个多边形,求里面的一个点,其距离离多边形的边界最远,也就是多边形中最大半径圆。 可以使用半平面交+二分法解。二分这个距离,边向内逼近,直到达到精度。
POJ 3384 Feng Shui (推荐) achttp://acm.pku.edu.cn/JudgeOnline/problem?id=3384 半平面交实际应用,用两个圆覆盖一个多边形,问最多能覆盖多边形的面积。 解法:用半平面交将多边形的每条边一起向“内”推进R,得到新的多边形,然后求多边形的最远两点。
POJ 1755 Triathlon (推荐)http://acm.pku.edu.cn/JudgeOnline/problem?id=1755 半平面交判断不等式是否有解。注意不等式在转化时正负号的选择,这直接影响到半平面交的方向。
POJ 2540 Hotter Colderhttp://acm.pku.edu.cn/JudgeOnline/problem?id=2540 半平面交求线性规划可行区域的面积。
POJ 2451 Uyuw's Concerthttp://acm.pku.edu.cn/JudgeOnline/problem?id=2451 Zzy专为他那篇nlogn算法解决半平面交问题的论文而出的题目。
五。计算几何背景,实际上解题的关键是其他问题(数据结构、组合数学,或者是枚举思想) 若干道经典的离散化+扫描线的题目,ACM选手必做题目
POJ 1151 Atlantis (推荐) achttp://acm.pku.edu.cn/JudgeOnline/problem?id=1151 POJ 1389 Area of Simple Polygonshttp://acm.pku.edu.cn/JudgeOnline/problem?id=1389 矩形离散化,线段树处理,矩形面积求交
POJ 1177 Picture (推荐)achttp://acm.pku.edu.cn/JudgeOnline/problem?id=1177 矩形离散化,线段树处理,矩形交的周长,这个题目的数据比较强。线段树必须高效。
POJ 3565 Ants (推荐)http://acm.pku.edu.cn/JudgeOnline/problem?id=3565 计算几何中的调整思想,有点像排序。要用到线段相交的判断。 详见:http://hi.baidu.com/novosbirsk/blog/item/fb668cf0f362bec47931aae2.html
POJ 3695 Rectangleshttp://acm.pku.edu.cn/JudgeOnline/problem?id=3695 又是矩形交的面积,但是由于是多次查询,而且矩形不多,使用组合数学中的容斥原理解决之最适合。线段树是通法,但是除了线段树,还有其他可行的方法。
POJ 2002 Squareshttp://acm.pku.edu.cn/JudgeOnline/problem?id=2002 枚举思想,求平面上若干个点最多能组成多少个正方形,点的Hash
POJ 1434 Fill the Cisterns!(推荐)http://acm.pku.edu.cn/JudgeOnline/problem?id=1434 一开始发昏了,准备弄个线段树。其实只是个简单的二分。
六。随机算法 POJ 2420 A Star not a Tree?http://acm.pku.edu.cn/JudgeOnline/problem?id=2420 多边形的费马点。所谓费马点,就是多边形中一个点P,该点到其他点的距离之和最短。四边形以上的多边形没有公式求费马点,因此可以使用随机化变步长贪心法。 详见:http://hi.baidu.com/novosbirsk/blog/item/75983f138499f825dd54019b.html
七。解析几何 这种题目本人不擅长,所以做得不多,模板很重要。当然,熟练运用叉积、点积的性质还是很有用的。 POJ 1375 Intervalshttp://acm.pku.edu.cn/JudgeOnline/problem?id=1375 知识点:过圆外一点求与圆的切线
POJ 1329 Circle Through Three Points achttp://acm.pku.edu.cn/JudgeOnline/problem?id=1329 求三角形外接圆
POJ 2354 Titanichttp://acm.pku.edu.cn/JudgeOnline/problem?id=2354 求球面上两个点的距离,而且给的是地理经纬坐标。
POJ 1106 Transmittershttp://acm.pku.edu.cn/JudgeOnline/problem?id=1106 角度排序,知道斜率求角度,使用atan函数。
POJ 1673 EXOCENTER OF A TRIANGLEhttp://acm.pku.edu.cn/JudgeOnline/problem?id=1673 可以转化为三角形的垂心问题。
八。旋转卡壳
POJ 2187 Beauty Contest achttp://acm.pku.edu.cn/JudgeOnline/problem?id=2187 凸包求最远点对。可以暴力枚举,也可以使用旋转卡壳。
POJ 3608 Bridge Across Islands(难)achttp://acm.pku.edu.cn/JudgeOnline/problem?id=3608 两个凸包的最近距离。本人的卡壳始终WA。郁闷。
九。其他问题 POJ 1981 Circle and Pointshttp://acm.pku.edu.cn/JudgeOnline/problem?id=1981 求单位圆最多能覆盖平面上多少个点
您还没有登录,请您登录后再发表评论
计算几何大汇总 很多资料的 算法 对于提高算法能力必不可少的 资料很多 ,分高点
计算几何计算几何计算几何计算几何计算几何计算几何计算几何计算几何计算几何计算几何计算几何计算几何计算几何计算几何计算几何计算几何计算几何
几何光学PPT几何光学PPT几何光学PPT几何光学PPT
“几何图霸”是一个用于绘制动态几何图形,辅助中学师生进行数学教学、探索和创造的优秀软件。“几何图霸”的特色是三维动态。它类似于几何画板,具有动态变换功能,自由拖动图元仍能保持几何关系不变。它区别于几何...
莫斯科大学数学教程,几何讲义++第一学期++解析几何。该书是根据在莫斯科大学力学数学系开设几何学课程时的讲义写成的。内容包括线性空间、直线与平面的仿射几何、欧氏空间几何、二次曲线与二次曲面、仿射与射影几何...
高等几何PPT高等几何PPT高等几何PPT高等几何PPT高等几何PPT高等几何PPT高等几何PPT高等几何PPT高等几何PPT高等几何PPT高等几何PPT高等几何PPT高等几何PPT高等几何PPT高等几何PPT高等几何PPT高等几何PPT高等几何PPT...
长期从事微分几何方向的研究工作和教学工作,开设的课程有“微分几何”、“微分流形”、“黎曼几何引论”和“纤维丛的微分几何”等。已出版的著作有:《微分几何讲义》(与陈省身合著),《黎曼几何选讲》(与伍鸿熙...
初中数学:经典几何模型大汇总扫描版.pdf
《几何学教程(立体几何卷)》J.Hadamard著,中文PDF版,清晰扫描版。该书除详细而严格地论述了立体几何内容外,还包括了常用曲线、测量概念以及有关高等几何等内容,附有大量的习题及解答。
计算几何 算法几何 几何算法 算法几何 算法几何
师范院校学生必读师范院校学生必读师范院校学生必读师范院校学生必读师范院校学生必读师范院校学生必读师范院校学生必读师范院校学生必读师范院校学生必读师范院校学生必读师范院校学生必读师范院校学生必读师范院校...
分形几何学是一门以不规则几何形态为研究对象的几何学。相对于传统几何学的研究对象为整数维数,如,零维的点、一维的线、二维的面、三维的立体乃至四维的时空。分形几何学的研究对象为非负实数维数,如0.63、1.58、...
将几何画板转换成EXE文件,这样运行几何画板文件就不需要安装几何画板了
空间解析几何与微分几何 第一章 向量 第二章 平面与直线 第三章 二次曲面 第四章 等距变换 正交变换 仿射变换 第五章 射影平面 第六章 练习题 第七章 局部曲线论 第八章 整体曲线论 第九章 局部曲面论
Alex Kendall 牛津大学专题研讨会讲义。主要讲述,如何建立不确定性模型;如何使用bayesian deep learning来构建不确定性模型;如何将模型应用于回归分类任务;如何利用几何信息来构造深度学习模型。
几何画板最强中文永久免费5.06版本安装包下载解压安装即可几何画板最强中文永久免费5.06版本安装包下载解压安装即可几何画板最强中文永久免费5.06版本安装包下载解压安装即可几何画板最强中文永久免费5.06版本安装包...
齐次坐标与几何变换 齐次坐标与几何变换 齐次坐标与几何变换 齐次坐标与几何变换
初中数学:经典几何模型大汇总(扫描版).pdf
十大高中平面几何几何定理汇总与证明.doc
相关推荐
计算几何大汇总 很多资料的 算法 对于提高算法能力必不可少的 资料很多 ,分高点
计算几何计算几何计算几何计算几何计算几何计算几何计算几何计算几何计算几何计算几何计算几何计算几何计算几何计算几何计算几何计算几何计算几何
几何光学PPT几何光学PPT几何光学PPT几何光学PPT
“几何图霸”是一个用于绘制动态几何图形,辅助中学师生进行数学教学、探索和创造的优秀软件。“几何图霸”的特色是三维动态。它类似于几何画板,具有动态变换功能,自由拖动图元仍能保持几何关系不变。它区别于几何...
莫斯科大学数学教程,几何讲义++第一学期++解析几何。该书是根据在莫斯科大学力学数学系开设几何学课程时的讲义写成的。内容包括线性空间、直线与平面的仿射几何、欧氏空间几何、二次曲线与二次曲面、仿射与射影几何...
高等几何PPT高等几何PPT高等几何PPT高等几何PPT高等几何PPT高等几何PPT高等几何PPT高等几何PPT高等几何PPT高等几何PPT高等几何PPT高等几何PPT高等几何PPT高等几何PPT高等几何PPT高等几何PPT高等几何PPT高等几何PPT...
长期从事微分几何方向的研究工作和教学工作,开设的课程有“微分几何”、“微分流形”、“黎曼几何引论”和“纤维丛的微分几何”等。已出版的著作有:《微分几何讲义》(与陈省身合著),《黎曼几何选讲》(与伍鸿熙...
初中数学:经典几何模型大汇总扫描版.pdf
《几何学教程(立体几何卷)》J.Hadamard著,中文PDF版,清晰扫描版。该书除详细而严格地论述了立体几何内容外,还包括了常用曲线、测量概念以及有关高等几何等内容,附有大量的习题及解答。
计算几何 算法几何 几何算法 算法几何 算法几何
师范院校学生必读师范院校学生必读师范院校学生必读师范院校学生必读师范院校学生必读师范院校学生必读师范院校学生必读师范院校学生必读师范院校学生必读师范院校学生必读师范院校学生必读师范院校学生必读师范院校...
分形几何学是一门以不规则几何形态为研究对象的几何学。相对于传统几何学的研究对象为整数维数,如,零维的点、一维的线、二维的面、三维的立体乃至四维的时空。分形几何学的研究对象为非负实数维数,如0.63、1.58、...
将几何画板转换成EXE文件,这样运行几何画板文件就不需要安装几何画板了
空间解析几何与微分几何 第一章 向量 第二章 平面与直线 第三章 二次曲面 第四章 等距变换 正交变换 仿射变换 第五章 射影平面 第六章 练习题 第七章 局部曲线论 第八章 整体曲线论 第九章 局部曲面论
Alex Kendall 牛津大学专题研讨会讲义。主要讲述,如何建立不确定性模型;如何使用bayesian deep learning来构建不确定性模型;如何将模型应用于回归分类任务;如何利用几何信息来构造深度学习模型。
几何画板最强中文永久免费5.06版本安装包下载解压安装即可几何画板最强中文永久免费5.06版本安装包下载解压安装即可几何画板最强中文永久免费5.06版本安装包下载解压安装即可几何画板最强中文永久免费5.06版本安装包...
齐次坐标与几何变换 齐次坐标与几何变换 齐次坐标与几何变换 齐次坐标与几何变换
初中数学:经典几何模型大汇总(扫描版).pdf
十大高中平面几何几何定理汇总与证明.doc