计算几何专题.ppt
《计算几何专题.ppt》由会员分享,可在线阅读,更多相关《计算几何专题.ppt(84页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、2013年ACM暑期集训计算几何专题 10级 赖鹏飞浙江师范大学ACM集训队2013.8.3 概述 特点特点 思考繁琐思考繁琐 编程繁琐编程繁琐 细节繁琐细节繁琐 如何把握如何把握 需要在平时将计算几何的相关子需要在平时将计算几何的相关子问题透彻研究问题透彻研究 模板的代码一定要规范模板的代码一定要规范 赛场上重点想思路,不能将时间赛场上重点想思路,不能将时间花在纠缠细节上(否则花在纠缠细节上(否则finish eggfinish egg)需要注意的细节(1 1)常用头文件常用头文件#include#include(2 2)计算几何中一般来说使用计算几何中一般来说使用doubledouble型
2、比较型比较频繁,请注意数据类型的选择,该用实数的时频繁,请注意数据类型的选择,该用实数的时候就用候就用doubledouble,而,而floatfloat容易失去精度。容易失去精度。(3 3)判断判断doubledouble型的型的x x是否为是否为0 0,应当用,应当用xeps x-eps&x-eps(或者(或者fabs(x)epsfabs(x)eps),其中),其中epseps代代表某个精度,常常取表某个精度,常常取eps=0.00000eps=0.0000000001 1,还有其,还有其他类似情况也要注意他类似情况也要注意doubledouble类型的精度问题,类型的精度问题,int(x
3、+eps)int(x+eps),避免,避免x=4.999999999x=4.999999999 需要注意的细节(4 4)圆周率取圆周率取3.1415926543.141592654或者更精确,或者用或者更精确,或者用acosacos(-1(-1.0.0)角度制和弧度制的转换,角度制和弧度制的转换,C/C+C/C+中的三角函数均中的三角函数均为弧度制为弧度制(5 5)尽量少用除法,开方,三角函数,容易失去精度。尽量少用除法,开方,三角函数,容易失去精度。用除法时注意除数不为用除法时注意除数不为0 0,输出的时候要小心输出的时候要小心-0.00000-0.00000,比如,比如a=-0.00000
4、01a=-0.0000001,printf(printf(“%.5f%.5f”,a);,a);(6)(6)在使用反三角函数时,注意定义域的范围,如在使用反三角函数时,注意定义域的范围,如 acosacos(x x),当),当x x是你计算得到时可能会出现越界现象,是你计算得到时可能会出现越界现象,比如本来应该得到是比如本来应该得到是1 1,而你计算得到谁,而你计算得到谁1.00000000011.0000000001,这时这时acos(x)的值就会出错了,所以我们可以加一)的值就会出错了,所以我们可以加一句判断,句判断,if(fabs(x-1)eps|fabs(x+1)eps)x=round(
5、x)必备知识:必备知识:向量及其运算、点线段直线、三角形的性质、圆的相关计算例题讲解例题讲解:UVa 11178、UVALive 4757、UVALive 4838、UVA 11168、UVA 11796、POJ 1066 专题训练专题训练:多边形面积、凸包、多边形重心、点在多边形内的判定、正点多边形中的Pick公式 必备知识 向量及其运算简单的说,向量(vector)就是有大小有方向的量,如速度、位移等物理量都是向量。向量最基本的运算是加法、满足平行四边形法则。wvw+v 向量及其运算在平面坐标系下,向量和点一样,也用两个数x、y表示。struct Point /点的表示double x,y
6、;/Point(double x=0,double y=0):x(x),y(y);typedef Point Vector;/从程序实现上,Vector知识Point的别名 向量及其运算向量基本运算的代码实现向量基本运算的代码实现Vector operator+(Vector A,Vector B)/向量+向量=向量 点+向量=点return Vector(A.x+B.x,A.y+B.y);Vector operator-(Point A,Point B)/点-点=向量return Vector(A.x-B.x,A.y-B.y);Vector operator*(Vector A,double
7、 p)/点*数=向量return Vector(A.x*p,A.y*p);向量及其运算Vector operator/(Vector A,double p)/点/数=向量return Vector(A.x/p,A.y/p);bool operator (const Point&a,const Point&b)return a.xb.x|(a.x=b.x&a.yb.y);int dcmp(double x)if(fabs(x)eps)return 0;else if(x0)return-1;return 1;向量及其运算bool operator=(const Point&a,const Poi
8、nt&b)/判断两点是否相等return dcmp(a.x-b.x)=0&dcmp(a.y-b.y)=0;注意到上面“相等”函数用到了“三态函数”dcmp,减少了精度问题。另外,向量有一个所谓的极角,即从x轴正半轴旋转到该向量方向的角度。C标准库里atan2函数是用来求极角的,如向量(x,y)的极角就是atan2(y,x)(单位:弧度)。向量及其运算double Dot(Vector A,Vector B)/点积return A.x*B.x+A.y*B.y;double Length(Vector A)/模return sqrt(Dot(A,A);double Angle(Vector A,V
9、ector B)/夹角return acos(Dot(A,B)/Length(A)/Length(B);向量及其运算double Cross(Vector A,Vector B)/叉积 return A.x*B.y-A.y*B.x;double Area2(Point A,Point B,Point C)/三角形面积两倍return Cross(B-A,C-A);Vector Rotate(Vector A,double rad)/向量逆时针旋转return Vector(A.x*cos(rad)-A.y*sin(rad),A.x*sin(rad)+A.y*cos(rad);三角形的性质外心:
10、外接圆圆心,三条中垂线交点内心:内接圆圆心,三条角平分线交点重心:三条中线交点,注意其物理性质垂心:三条垂线焦点正弦公式:余弦公式:ABCDabc 三角形的性质中线公式:高线:角平分线公式:面积(海伦公式):外接圆半径:ABCDabc 三角形的性质内接圆半径:广义勾股定理:注:海伦公式推广到四边形婆罗摩笈多公式:ABCDabc点、线段、直线直线可以用直线上的一个点P0和方向向量v表示,直线所有的点P=P0+vt,其中t为参数。已知直线上面的两点A、B,则可表示直线方程为A+(A-B)t。优点:可以表示所有直线;可以通过限制参数来表示线段和射线1.直线的参数表示点、线段、直线设直线方程分别为P+
11、vt和Q+wt,设向量u=QP,交点在第一条直线的参数t1,第一条直线的参数t2,怎x和y坐标可列出一个方程,解得:2.相交直线交点点、线段、直线Point GetLineIntersection(Point P,Vector v,Point Q,Vector w)/两直线交点,点、向量表示直线Vector u=P-Q;double t=Cross(w,u)/Cross(v,w);return P+v*t;注:从上述公式可得,当P,v,Q,w各分量为有理数的时候,交点坐标也为有理数,当精度要求极高的情况下,可以考虑用自定义分数类;点、线段、直线点到直线的距离是很常用的函数,可用叉积计算的到,及
12、用平行四边形的面积除以底。代码如下:double DistanceToLine(Point P,Point A,Point B)/点到直线距离Vector v1=B-A,v2=P-A;return fabs(Cross(v1,v2)/Length(v1);2.点到直线的距离点、线段、直线double DistanceToSegment(Point P,Point A,Point B)if(A=B)return Length(P-A);Vector v1=B-A,v2=P-A,v3=P-B;if(dcmp(Dot(v1,v2)0)return Length(v3);else return fab
13、s(Cross(v1,v2)/Length(v1);3.点到线段的距离点、线段、直线我们定义“规范相交”为两条线段恰有一个交点,且不在任何一条线段的端点。每一条线段的两个端点都在另一条线段的两侧,可以用叉积的符号来判断;4.线段相交判定点、线段、直线bool SegmentProperIntersection(Point a1,Point a2,Point b1,Point b2)/线段相交判定(规范相交)double c1=Cross(a2-a1,b1-a1);double c2=Cross(a2-a1,b2-a1);double c3=Cross(b2-b1,a1-b1);double c
14、4=Cross(b2-b1,a2-b1);return dcmp(c1)*dcmp(c2)0&dcmp(c3)*dcmp(c4)0;点、线段、直线不规范相交时再判断端点的情况就好:bool OnSegment(Point p,Point a1,Point a2)/点与线段判定return dcmp(Cross(a1-p,a2-p)=0&dcmp(Dot(a1-p,a2-p)=r1+r2)printf(0.000n);/两圆相离或相外切 圆的相关计算 else if(d=0)/内切 if(r1r2)printf(%0.3lfn,PI*r2*r2);else printf(%0.3lfn,PI*r
15、1*r1);else A1=2*acos(d*d+r1*r1-r2*r2)/(2*d*r1);/求以圆心为顶点与两圆交点连线的角 A2=2*acos(d*d+r2*r2-r1*r1)/(2*d*r2);s1=0.5*r1*r1*sin(A1)+0.5*r2*r2*sin(A2);s2=A1/2*r1*r1+A2/2*r2*r2;s=s2-s1;printf(%0.3lfn,s);来试一试嘛来试一试嘛HDU 1798 Tell me the area(两圆相交面积)POJ 1269 Intersecting Lines(两直线关系)POJ 1118 Lining Up(最多共线点数)POJ 33
16、04 Segments(直线与线段关系)HDU 1071 The area(抛物线与直线所围面积)HDU 2105 The Center of Gravity(三角形重心)UVALive 5827 Regular Convex Polygon(三角形外心)POJ 4048 Chinese Repeating Crossbow(射线与线段关系)POJ 1410 Intersection(线段与矩形关系)POJ 2398 Toy Storage(点与直线关系)专题训练多边形面积给定一个简单多边形,求其面积。输入:多边形(顶点按逆时针顺序排列)输出:面积S基本问题(基本问题(1):):Any goo
17、d idea?多边形面积在解析几何里,ABC的面积可以通过如下方法求得:点坐标=边长 =海伦公式=面积缺点:缺点:计算量大精度损失三角形的面积:三角形的面积:多边形面积计算几何的方法:计算几何的方法:在计算几何里,我们知道,ABC的面积就是“向量AB”和“向量AC”两个向量叉积的绝对值的一半。其正负表示三角形顶点是在右手系还是左手系。ABC成左手系,负面积BCAABC成右手系,正面积CBA多边形面积Area(A,B,C)=1/2*(AB)(AC)=/2特别注意:以上得到是有向面积(有正负)有向面积(有正负)!Xb X a Yb Y aXc X a Yc Y a多边形面积凸多边形的三角形剖分很自
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 计算 几何 专题
限制150内