《计算几何专题WelcomeToPKUJudgeOnline计算几何专题欢迎来到北大在线评测》由会员分享，可在线阅读，更多相关《计算几何专题WelcomeToPKUJudgeOnline计算几何专题欢迎来到北大在线评测（13页珍藏版）》请在金锄头文库上搜索。
1、计算几何专题姚金宇Outline概述元素点，线，角，平面，半平面，圆，多边形，凸包公式叉积、点积、三角定理、面积定理算法求凸包、点与多边形的位置关系还能有啥？战略上蔑视之，战术上重视之概述特点思考繁琐编程繁琐细节繁琐如何把握需要在平时将计算几何的相关子问题透透彻研究模板的代码一定要规范范赛场上重点想思路思路，不能将时间花在纠缠细节上（否则finish egg）第一个问题：判断线段是否相交预备知识如何表示线段直线方程向量的表示向量的叉积方法解析方法与叉积判断法规范相交与非规范相交基本元素点与直线（解析几何是计算几何的基础！）点到直线距离（扩展：平行线间距离）直线平移角夹角：点积、余弦定理极角：叉
2、积、讨论圆两圆位置关系（外离、外切、相交、内切、内含、同心）第二个问题：点与多边形的位置关系预备知识多边形表示：是否按顺序，是何顺序凸多边形一般多边形是否可自交？点与多边形的位置分类形上、形内、行外扩展：点与凸多边形的位置关系问题多边形严格限制为m条边的凸多边形n个点，给出各自的判断凸多边形特性：左链、右链二分法复杂度O(nlogm)第三个问题：凸包计算几何经典问题为何求凸包的下界是O(nlogn)？凸包相关问题点与凸包位置关系（见问题二扩展）面积问题凸包与直线的最远点凸包与凸包的交凸包与其他算法（e.g.动态规划）第四个问题：半平面的交这是一个困难的问题O(n2)的解法O(nlogn)的解法例题给定n个黑色点，m个白色点。判断黑色点集与白色点集的位置关系。Case1: 可以用一条直线将二者分离Case2: 黑色凸包与白色凸包相交且不包含Case3: 黑色凸包包含于白色凸包Case4: 白色凸包包含于黑色凸包 练习题111312713521106620693502THE ENDThanks for your attention!
