ACM计算几何必看 (2).ppt
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进栈Sfor(i=3;i=m;+i)while(由S的栈顶元素的下一个元素、S的栈顶元素以及pi构成的折线段不拐向左侧)对S弹栈压pi进栈Sreturn S,凸包练习,1219:Triangle*需要先求凸包，之后不能用N3的算法穷举三角形，需要使用二分法POJ 1113 Wall POJ 2007 Scrambled Polygon POJ 1228 Grandpas Estate 凸包很重要，以上题目务必做出一题,计算几何的二分思想,二分法在计算几何中应用很多1140:Crossed ladders1485:Triangle Partition*,Further Exercise,1041:The Circumference of the Circle 1708:NKPC3找出公共区域*1412:Triangle Cuts*1981 Circle and Points*POJ 3129 How I Wonder What You Are!POJ 3130 How I Mathematician Wonder What You Are!*,
