ACM竞赛中的数学方法初步计算几何•所谓计算几何,一般就指向量方法来解几何问题.•为什么用向量?因为解析几何方法在很多时候都显得复杂,而且计算可能比较复杂,有精度损失问题.坐标法基础•计算几何都是以坐标化为前提的•必须知道一些基本的解析几何的方法.例如:两点距离的公式等向量的点积•向量a,b点积(又称内积)的几何意义是a在b(或b在a)上的投影长度(标量,注意可能为负值).计算方法是a·b=|a|·|b|·cosC,其中,C是向量a,b的夹角(下同).•若向量a=(x1,y1,z1),b=(x2,y2,z2),则a·b=x1x2+y1y2+z1z2•cosC可以由此计算出来应用•用于计算向量夹角.•判断两向量是否垂直•平面方程的向量形式:平面方程ax+by+cz=0(已通过移坐标轴去掉常数项),令平面法向量n=(a,b,c),点X(x,y,z),则平面方程记为n·X=0,实际上,如果平面过点P,则方程为n·(X-P)=0.应用(续)•还可以计算点P(x0,y0,z0)到平面n·X=0的距离.把n单位化,不妨仍记为n,把向量OP往n上投影,即可得距离d=|n·OP|.•判断P是否在平面的哪一边:n·OP为正时P在n指向的一侧,否则与n的指向相反向量叉积•叉积又称外积,a×b的结果是一个矢量,其数值是以a,b为边的平行四边形面积,即|a||b|sinC,其方向和a,b都垂直,并且,a,b,a×b构成右手系.•计算方法:222111,,,,,,zyxzyxkjiba应用•计算三角形或者平行四边形面积•计算点到直线(进一步,线段)的距离•判断向量(或者直线,线段)平行关系•内积和外积结合可以判断复杂的位置关系点的旋转变换•原来的点(x,y)和变换后的点(x’,y’)的坐标之间满足下面的公式:x’=xcosθ-ysinθy’=xsinθ+ycosθ–其中,θ是逆时针旋转的角度,这个公式适用于旋转点在原点的情况.球面距离•已知球半径R,球面上两点A,B的坐标A(x1,y1,z1),B(x2,y2,z2),球心在原点O,球面距离2arccosROBOARRd•已知两点的极坐标,–其中,为经度数,为纬度数,则可以证明球面距离为•极坐标与直角坐标之间的换算关系:其中,θ是纬度,φ是经度•已知极坐标,也可以先用上面的公式计算直角坐标,然后算球面距离,但是会有精度损失coscoscossinsinxRyRzR计算几何进一步的话题•内容很丰富,以上列举的是基本的武器•参加ACM竞赛至少还需要了解二维凸包的算法(比较复杂)例题•BOJ1012TheCircumferenceoftheCircle•给出了三个点的坐标，请输出由这三个点所确定的圆的周长，结果保留二位小数•如图,关键是求出外接圆半径RABC•可以由向量外积算出面积s,并得到sinA.•由正弦定理,a/sinA=2R•由此可以计算外接圆面积ABCabcBOJ1062PolygonProgrammingwithEase•给了n边形的n条边的中点,求n个顶点的坐标,n是奇数•可以建立两个(x坐标和y坐标)联系n个顶点和n个中点的n元一次方程组,注意到n是奇数,这样的方程有唯一解另一种思路•可以证明以下事实:将一个n边形依次以其每边中点为对称中心做中心对称(反射)变换,n次变换之后,等价于对此多边形做了一个以第一个顶点为中心,180度的旋转变换.•可以任意选定一个点p,依次对每个中心做反射变换,n次之后得到q,则第一个顶点是(p+q)/2,由此可以得到其它顶点BOJ1054Equidistance•给定球面两点A,B的极坐标,再给定第三点P的极坐标,求球面上到A,B两点距离相等的点(组成一个大圆O1)到P点的最短球面距离•首先,把极坐标转换成直角坐标.以a,b,p代表A,B,P对应的向量.•到A,B距离相等的点集构成一个平面,法向量是a-b,过点(a+b)/2,圆O1在这个平面上•向量a-b和p之间的夹角theta可以比较容易计算出来(使用内积方法和反三角函数),用球半径乘以theta的余角即可以得出所求球面距离.•注意特殊情况:如果AB两点重合,则整个球面上的点到AB的距离都是相等的,那么P点到AB的距离也是相等的,所以此时所求的球面距离为P到自身的距离,为零.需要单独处理BOJ1059BalancedFood•给了扇形的桌子和其上的圆形pizza的位置和大小,pizza被切成若干块(第一刀是沿x轴正向来切的),求一个取pizza的顺序,使得pizza不从桌子上掉下来•如右图,左边的两块pizza先取下面的后取上面的,可以不掉下来,右边的pizza一定会掉下来扇形重心公式•如果剩下的pizza的重心不在桌子上,pizza会掉下来.剩下的pizza的重心就是所有pizza片...
