ACM计算几何必看.ppt

  1. 1、本文档共25页,可阅读全部内容。
  2. 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
  3. 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载
  4. 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
ACM计算几何必看

2007年ACM协会暑期集训专题(三) 计算几何 刁瑞 数学科学学院 需要注意的细节 常用头文件#includemath.h 计算几何中一般来说使用double型比较频繁,请注意数据类型的选择,该用实数的时候就用double,而float容易失去精度。 判断double型的x是否为0,应当用xeps 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); 向量及其运算 计算几何中经常使用向量,而且基本上都是二维的,下面用αβγ代表三个向量 α=(x[0],y[0]) β=(x[1],y[1]) γ=(x[2],y[2]) 某些题目需要经常使用向量运算,因此对于这类问题最好建立构造类型或者类来表示向量,并将向量之间的运算进行重载 一般需要重载加法,减法,和向量乘法 向量及其运算 struct point{ //构造点的数据类型,也可作向量使用 double x; double y; }v1,v2; point operator+(point p1,point p2); double operator*(point p1,point p2); 向量及其运算 向量有两种乘法,内积(数量积,点积)和外积(向量积,叉积),一般是要根据题目需要选择其中一个重载,多数情况是重载外积,其中 内积α·β= x[0]*x[1] + y[0]*y[1] 外积α×β= x[0]*y[1] – x[1]*y[0]= 向量及其运算 内积的几何意义:α在β的投影α’与β的长度乘积 外积的几何意义:α和β所张成的平行四边形的有向面积 外积在计算几何的题目当中经常使用 外积的应用 判断外积的符号,右手定则 如图,α×β0,β×α0 如果α×β== 0 则等价于两个向量共线(同向或反向),可以用此判断三点共线问题。当然,这里的==0在实际编程的时候要用一个精度来控制 外积的应用 考察右图 有向线段P1P2 “向右拐” 得到P2P3 有向线段P1P2 “向左拐” 得到P2P4 可以利用外积判断“拐向”,这在求凸包时会用到 外积的应用 利用外积求三角形面积 已知三个顶点坐标为(a[0],b[0]),(a[1],b[1]),(a[2],b[2]),则三角形面积为 注意别忘记取绝对值,这里利用面积是否为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相交,其中

文档评论(0)

shaoye348 + 关注
实名认证
内容提供者

该用户很懒,什么也没介绍

1亿VIP精品文档

相关文档