ACM计算几何必看

《ACM计算几何必看》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、2007年ACM协会暑期集训专题(三)计算几何刁瑞数学科学学院需要注意的细节常用头文件#include计算几何中一般来说使用double型比较频繁，请注意数据类型的选择，该用实数的时候就用double，而float容易失去精度。判断double型的x是否为0，应当用x-eps（或者fabs(x)

2、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])某些题目需要经常使用向量运算，因此对于这类问题最好建立构造类型或者类来表示向量，并将向量之间的运算进行重载一般需要重载加法，减法，和向量乘法向量及其运算structp

3、oint{//构造点的数据类型，也可作向量使用doublex;doubley;}v1,v2;pointoperator+(pointp1,pointp2);doubleoperator*(pointp1,pointp2);向量及其运算向量有两种乘法，内积（数量积，点积）和外积（向量积，叉积），一般是要根据题目需要选择其中一个重载，多数情况是重载外积，其中内积α·β=x[0]*x[1]+y[0]*y[1]外积α×β=x[0]*y[1]–x[1]*y[0]=向量及其运算内积的几何意义：α在β的投影α’与β的长度乘积外积的几何意义：α和β所张成的平行四边形的有向

4、面积外积在计算几何的题目当中经常使用外积的应用判断外积的符号，右手定则如图，α×β<0，β×α>0如果α×β==0则等价于两个向量共线（同向或反向），可以用此判断三点共线问题。当然，这里的==0在实际编程的时候要用一个精度来控制外积的应用考察右图有向线段P1P2“向右拐”得到P2P3有向线段P1P2“向左拐”得到P2P4可以利用外积判断“拐向”，这在求凸包时会用到外积的应用利用外积求三角形面积已知三个顶点坐标为(a[0],b[0]),(a[1],b[1]),(a[2],b[2])，则三角形面积为注意别忘记取绝对值，这里利用面积是否为0也可以考察三点

5、共线问题这个方法求面积比海伦公式或者其他方法要好外积的应用由求三角形面积的方法可以推广求凸多边形面积如图，从一固定点出发，向其他各点引辅助线，这样就分割成了若干个三角形，利用上式求出每个三角形的面积再相加即可。整点多边形整点多边形是指顶点的横纵坐标均为整数由外积导出的面积计算公式可以看出，整点多边形的面积或为整数，或为整数/2.Pick公式：整点多边形的面积=内部整点个数+边上的整点个数/2-1.NKOJ1159:Triangle计算几何中的公式有不少，需要积累三角形的一些性质如何判断点是否在三角形内部？此点与三角形三个顶点相连，出现三个三角形，如果这三个

6、三角形的面积之和等于原三角形面积，那么该点在内部推广：可用来判断点是否在凸多边形内部思考：如何判断点是否在一般多边形内部？三角形的心外心：外接圆圆心，三条中垂线交点内心：内接圆圆心，三条角平分线交点重心：三条中线交点，注意其物理性质垂心：三条垂线焦点旁心：一个外交平分线与另外两个内角平分线交点NKOJ1257:EXOCENTEROFATRIANGLE判断点在直线上利用三点共线的等价条件α×β==0直线上取两不同点P1,P2，若点P在直线上，则fabs((P1-P)×(P2-P))

7、积是否

8、min(x3,x4)<=max(x1,x2)&&min(y1,y