已阅读5页,还剩20页未读, 继续免费阅读
版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
2007年ACM协会暑期集训专题(三) 计算几何,刁瑞 数学科学学院,需要注意的细节,常用头文件#include 计算几何中一般来说使用double型比较频繁,请注意数据类型的选择,该用实数的时候就用double,而float容易失去精度。 判断double型的x是否为0,应当用x-eps(或者fabs(x)eps),其中eps代表某个精度,常常取eps=0.000001,还有其他类似情况也要注意double类型的精度问题,int(x+eps),避免x=4.999999999,需要注意的细节,圆周率取3.141592654或者更精确,或者用acos(-1) 角度制和弧度制的转换,C/C+中的三角函数均为弧度制 尽量少用除法,开方,三角函数,容易失去精度。用除法时注意除数不为0 输出的时候要小心-0.00000,比如 a=-0.0000001,printf(“%.5lf”,a);,向量及其运算,计算几何中经常使用向量,而且基本上都是二维的,下面用代表三个向量 =(x0,y0) =(x1,y1) =(x2,y2) 某些题目需要经常使用向量运算,因此对于这类问题最好建立构造类型或者类来表示向量,并将向量之间的运算进行重载 一般需要重载加法,减法,和向量乘法,向量及其运算,struct point /构造点的数据类型,也可作向量使用 double x; double y; v1,v2; point operator+(point p1,point p2); double operator*(point p1,point p2);,向量及其运算,向量有两种乘法,内积(数量积,点积)和外积(向量积,叉积),一般是要根据题目需要选择其中一个重载,多数情况是重载外积,其中 内积= x0*x1 + y0*y1 外积= x0*y1 x1*y0=,向量及其运算,内积的几何意义:在的投影与的长度乘积 外积的几何意义:和所张成的平行四边形的有向面积 外积在计算几何的题目当中经常使用,外积的应用,判断外积的符号,右手定则 如图,0 如果= 0 则等价于两个向量共线(同向或反向),可以用此判断三点共线问题。当然,这里的=0在实际编程的时候要用一个精度来控制,外积的应用,考察右图 有向线段P1P2 “向右拐” 得到P2P3 有向线段P1P2 “向左拐” 得到P2P4 可以利用外积判断“拐向”,这在求凸包时会用到,外积的应用,利用外积求三角形面积 已知三个顶点坐标为(a0,b0),(a1,b1),(a2,b2),则三角形面积为 注意别忘记取绝对值,这里利用面积是否为0也可以考察三点共线问题 这个方法求面积比海伦公式或者其他方法要好,外积的应用,由求三角形面积的方法可以推广求凸多边形面积 如图,从一固定点出发,向其他各点引辅助线,这样就分割成了若干个三角形,利用上式求出每个三角形的面积再相加即可。,整点多边形,整点多边形是指顶点的横纵坐标均为整数 由外积导出的面积计算公式可以看出,整点多边形的面积或为整数,或为整数/2. Pick公式:整点多边形的面积=内部整点个数+边上的整点个数/2 - 1. NKOJ 1159: Triangle 计算几何中的公式有不少,需要积累,三角形的一些性质,如何判断点是否在三角形内部? 此点与三角形三个顶点相连,出现三个三角形,如果这三个三角形的面积之和等于原三角形面积,那么该点在内部 推广:可用来判断点是否在凸多边形内部 思考:如何判断点是否在一般多边形内部?,三角形的心,外心:外接圆圆心,三条中垂线交点 内心:内接圆圆心,三条角平分线交点 重心:三条中线交点,注意其物理性质 垂心:三条垂线焦点 旁心:一个外交平分线与另外两个内角平分线交点 NKOJ 1257: EXOCENTER OF A TRIANGLE,判断点在直线上,利用三点共线的等价条件= 0 直线上取两不同点P1,P2,若点P在直线上,则fabs(P1 - P) (P2 - P ) eps 如果该题目需要编写求三角形面积的函数,那直接判断这三个点形成的三角形面积是否eps,判断点在线段上,判断点P(x,y)是否在线段P1P2上,其中P1(x1,y1),P2(x2,y2) 需要验证两条 (1)点P在P1P2所在直线上,即三点共线 (2)点P在P1P2为对角线的矩形内 其中(2)利用 min(x1,x2)=x=max(x1,x2) & min(y1,y2)=y=max(y1,y2),判断两线段是否相交,判断P1P2是否和P3P4相交,其中Pi坐标为(xi,yi),同样需要满足两个条件 (1)快速排斥试验: 以P1P2为对角线的矩形S1是否和以P3P4为对角线的矩形S2相交,即 min(x1,x2)=max(x3,x4) & min(x3,x4)=max(x1,x2) & min(y1,y2)=max(y3,y4) & min(y3,y4)=max(y1,y2),判断两线段是否相交,(2)跨立试验: 点P1,P2必然在线段P3P4的不同侧,因此 点P3,P4必然在线段P1P2的不同侧,因此,第一个不等式等价于线段P1P2与直线P3P4相交,第二个不等式等价于线段P3P4和直线P1P2相交,两条关系为&, 1015 土地划分,快速排斥试验引申,思考: 简单的改造一下就可以用来判断一个矩形是否在另一个矩形内部 NKOJ 1177 rectangles,凸包,convex hull 是指对于平面上给定的一些点,选取一个最小的凸多边形使得这些点或者在其内部,或者在其边上,求凸包的Graham扫描法,对于一个有三个或以上点的点集Q 令p0为Q中Y-X坐标排序下最小的点 设为对其余点按以p0为中心的极角逆时针排序所得的点集(如果有多个点有相同的极角,除了距p0最远的点外全部移除) 压p0进栈S,压p1进栈S,压p2进栈S for(i=3;i=m;+i) while(由S的栈顶元素的下一个元素、S的栈顶元素以及pi构成的折线段不拐向左侧) 对S弹栈 压pi进栈S return S,凸包练习,1219: Triangle * 需要先求凸包,之后不能用N3的算法穷举三角形,需要使用二分法 POJ 1113 Wall POJ 2007 Scrambled Polygon POJ 1228 Grandpas Estate 凸包很重要,以上题目务必做出一题,计算几何的二分思想,二分法在计算几何中应用很多 1140: Crossed ladders 1485: Triangle Partition *,Further Exercise,1041: The Circumference of the Circle 1708: NK
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 《我们在呼吸导学案-2023-2024学年科学大象版2001》
- 《养植物作业设计方案-2023-2024学年科学人教鄂教版》
- 《幼儿园的任务作业设计方案》
- 旅游地理高考真题及答案(2008-2017年)-文档
- 《太阳和影子作业设计方案-2023-2024学年科学青岛版五四学制》
- 《水面的秘密》导学案-2023-2024学年科学青岛版2001
- 《培养坚强的意志品质作业设计方案》
- 《节奏与旋律作业设计方案-2023-2024学年初中道德与法治统编版》
- 《浣溪沙(身向云山那畔行)-纳兰性德作业设计方案-2023-2024学年初中语文统编版》
- 《不同环境中的动物导学案-2023-2024学年科学人教鄂教版》
- 大学美育 第2版 课件 第七章 造型艺术与美育
- 镀锌水管施工方案
- 沙曲一号煤矿“12.13”井下煤仓较大事故专项安全风险辨识评估报告
- 安全管理之重点部位防火安全措施
- 输血相关制度
- 2023河南省气象部门招聘应届高校毕业生21人笔试参考题库(共500题)答案详解版
- 2023中国暴雨强度公式汇总
- 红楼梦:财富的变幻
- 医联体建设管理制度范本
- 尿失禁护理指南
- 表-D完整版本.0.2-作业架施工验收记录表
评论
0/150
提交评论