计算几何专题 (2).ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,2013年ACM暑期集训,计算几何专题,10级,赖鹏飞,浙江师范大学ACM集训队,2013.8.3,概述,特点,思考繁琐,编程繁琐,细节繁琐,如何把握,需要在平时将计算几何的相关子问题透彻研究,模板的代码一定要规范,赛场上重点想思路，不能将时间花在纠缠细节上（否则finish egg）,需要注意的细节,（1）,常用头文件#include,（2）,计算几何中一般来说使用double型比较频繁，请注意数据类型的选择，该用实数的时候就用double，而float容易失去精度。,（3）,判断double型的x是否为0，应当用x-eps（或者fabs(x)eps），其中eps代表某个精度，常常取eps=0.00000,00,1，还有其他类似情况也要注意double类型的精度问题，int(x+eps)，避免x=4.999999999,需要注意的细节,（4）,圆周率取3.141592654或者更精确，或者用acos(-1,.0,)角度制和弧度制的转换，C/C+中的三角函数均为弧度制,（5）,尽量少用除法，开方，三角函数，容易失去精度。用除法时注意除数不为0,，,输出的时候要小心-0.00000，比如a=-0.0000001，printf(,“,%.5f,”,a);,(6)在使用反三角函数时，注意定义域的范围，如 acos（x），当x是你计算得到时可能会出现越界现象，比如本来应该得到是1，而你计算得到谁1.0000000001，,这时,acos（x）的值就会出错了，所以我们可以加一句判断，if(fabs(x-1)eps|fabs(x+1)eps)x=round（x）,必备知识：,向量及其运算、点线段直线、三角形的性质、圆的相关计算,例题讲解,：,UVa 11178、UVALive 4757、UVALive 4838、UVA 11168、UVA 11796、,POJ 1066,专题训练,：,多边形面积、凸包、多边形重心、点在多边形内的判定、正点多边形中的,Pick公式,必备知识,向量及其运算,简单的说，向量（vector）就是有大小有方向的量，如速度、位移等物理量都是向量。向量最基本的运算是加法、满足平行四边形法则。,w,v,w+v,向量及其运算,在平面坐标系下，向量和点一样，也用两个数x、y表示。,struct Point,/点的表示,double x,y;,/,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 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,int dcmp(double x),if(fabs(x)eps)return 0;,else if(x0)return-1;,return 1;,向量及其运算,bool operator=(const Point&a,const Point&b)/判断两点是否相等,return dcmp(a.x-b.x)=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,Vector 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);,三角形的性质,外心：外接圆圆心，三条中垂线交点,内心：内接圆圆心，三条角平分线交点,重心：三条中线交点，注意其物理性质,垂心：三条垂线焦点,正弦公式：,余弦公式：,A,B,C,D,a,b,c,三角形的性质,中线公式：,高线：,角平分线公式：,面积（海伦公式）：,外接圆半径：,A,B,C,D,a,b,c,三角形的性质,内接圆半径：,广义勾股定理：,注：海伦公式推广到四边形,婆罗摩笈多公式：,A,B,C,D,a,b,c,点、线段、直线,直线可以用直线上的一个点P0和方向向量v表示，直线所有的点P=P0+vt，其中t为参数。已知直线上面的两点A、B，则可表示直线方程为A+（A-B)t。,优点：可以表示所有直线；,可以通过限制参数来表示线段和射线,1,.,直线的参数表示,点、线段、直线,设直线方程分别为P+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各分量为有理数的时候，交点坐标也为有理数，当精度要求极高的情况下，可以考虑用自定义分数类；,点、线段、直线,点到直线的距离是很常用的函数，可用叉积计算的到，及用平行四边形的面积除以底。代码如下：,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 fabs(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 c4=Cross(b2-b1,a2-b1);,return dcmp(c1)*dcmp(c2)=r1+r2)printf(0.000n);/两圆相离或相外切,圆的相关计算,else if(d=0),/内切,if(r1r2)printf(%0.3lfn,PI*r2*r2);,else printf(%0.3lfn,PI*r1*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 3304 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 good idea?,多边形面积,在解析几何里，ABC的面积可以通过如下方法求得,：,点坐标=边长 =海伦公式=面积,缺点：,计算量大,精度损失,三角形的面积：,多边形面积,计算几何的方法：,在计算几何里，我们知道，ABC的面积就是“向量AB”和“向量AC”两个向量叉积的绝对值的一半。其正负表示三角形顶点是在右手系还是左手系。,ABC成左手系，负面积,B,C,A,ABC成右手系，正面积,C,B,A,多边形面积,Area(A,B,C)=1/2*(AB)(AC),=/2,特别注意：,以上得到是,有向面积（有正负）,！,Xb X a Yb Y a,Xc X a Yc Y a,多边形面积,凸多边形的三角形剖分,很自然地，我们会想到以 P1为扇面中心，连接P1Pi就得到N-2个三角形，由于凸性，保证这些三角形全在多边形内，那么，这个凸多边形的有向面积：,A=sigma(Ai)(i=1N-2),P1,P2,P3,P4,P5,P6,A1,A2,A3,A4,多边形面积,凹多边形的面积,P1,P4,P3,P2,多边形面积,任意点为扇心的三角形剖分：,我们能把多边形分成N-2个三角形，为什么不能分成N个三角形呢？,比如，以多边形内部的一个点为扇心，就可以把多边形剖分成 N个三角形。,P1,P2,P6,P5,P4,P3,多边形面积,前面的三角剖分显然对于多边形内部任意一点都是合适的！,（把分割点放在原点？）,我们可以得到：A=sigma(Ai)（i=1,N,）,即：,A=,sigma,/2,（i=1,N,）,Xi X0,Yi Y0,X(i+1)X0,Y(i+1)Y0,点在多边形内的判定,方法一：射线法,从判定点任意引一条射线，如果和边界的交点是奇数次，说明点在多边形内，如果交点为偶数个，点在多边形外。在多边形上需另外判断。,方法二：转角法,计算多边形每条边的转角的和，如果为360度，则点在多边形内，如果为0度，则在多边形外，如果为180度则点在多边形上（也适合非简单多边形）。,点在多边形内的判定,如果按照上面的定义实现，需要计算大量的反三角函数，不仅速度慢，而且容易产生精度误差。我们一般假设一条向右的射线，统计多边形穿过这条射线的正反次数，把这个数记为绕数wn（Winging Number），逆时针穿过是wn+，顺时针穿过wn-。,注意在程序现实的时候，判断是否穿过，以及穿过方向时，需要用叉积判断输入点在边的左边还是右边。,点在多边形内的判定,int isPointInPolygon(Point p,Polyon poly),int w=0,n=v.size();,for(int i=0;i0,if(k0)wn-;,if(wn!=0)return 1;/内部,return 0;/外部,凸包,顾名思义，凸包就是把给定点包围在内部、面积最小的图多边形，它在计算几何里有着极其重要的作用。,凸包,在网上可以找到很多关于凸包的算法的资料，这里我们简单叙述一下基于水平序的Andrew算法。,首先把所有的点按照x从小到大排列（x相同，按y,从小到大排列,），删除重复点得到序列p1，p2，然后把p1，p2放到凸包中，从p3开始，当新点在凸包“前进”方向的左边时继续前进，否则依次删除最近加入凸包的点，直到新点在左边。,凸包,如图，新点p18在向量p10p15（即当前前进方向）的右边，因此需要从凸包上删除p15和p10，让p8的下一个点为p18。重复上述过程，直到碰到最右边的点pn，就求得了“下凸包”。然后反过来从pn开始再做一遍，求出“上凸包”，合并起来就是完整的凸包了。,p5,p8,p10,p15,p18,p5,p8,p10,p15,p18,凸包,int ConvexHull(Point*p,int n,Point*ch),sort(p,p+n);,int m=0;,for(int i=0;i1,chm+=pi;,int k=m;,for(int i=n-1;i=0;i-),while(mk,chm+=pi;,if(n)m-;,return m;,多边形的重心,给定一个简单多边形，求其重心。,输入,：多边形（顶点按逆时针顺序排列）,输出,：重心点C,多边形的重心,从三角形的重心谈起：,三角形的重心是：,(x1+x2+x3)/3，(y1+y2+y3)/3,可以推广否？,Sigma(xi)/N,sigma(yi)/N (i=1N)?,多边形的重心,看看一个特例：,.,多边形的重心,原因：,错误的推广公式是,“,质点系重心公式,”,，即如果认为多边形的质量仅分布在其顶点上，且均匀分布，则这个公式是对的。,但是，现在多边形的质量是均匀分布在其内部区域上的，也就是说，是与面积有关的！,多边形的重心,Solution:,剖分成N个三角形，分别求出其重心和面积，这时可以想象，原来质量均匀分布在内部区域上，而现在质量仅仅分布在这N个重心点上（等假变换），这时候就可以利用刚才的质点系重心公式了。,不过，要稍微改一改，改成,加权平均,数，因为质量不是均匀分布的，每个质点代表其所在三角形，其质量就是该三角形的面积（,有向面积,！,），这就是权！,正点多边,形中的,Pick公式,问题描述：,给出一个正点多边形（格点多边形），,求多边形的面积,，,以为多边形内部的格点数目和多边形边上的格点数目。,正点多边,形中的,Pick公式,pick公式：,多边形的面积=多边形边上的格点数目/2+多边形内部的格点数目-1,对于每一条线段来说，,如果是水平或者垂直，显然可以得到，否则则是坐标差的最大公约数,加,1.,全部搞定！,UVA 12304 2D Geometry 110 in 1!,（综合）,POJ 1113 Wall（凸包周长）,POJ 3348 Cows（凸包面积）,POJ 1265 Area（简单格点多边形）,UVA 10652 Board Wrapping,（凸包）,例题分析,UVa 11178 Morleys Theorem,题目意思：,Morley定理是这样的：做三角形ABC每个内角的三等分线，相交成三角形DEF，则DEF是等边三角形，如图所示。,你的任务就是根据给定的A、B、C3个点的坐标来确定D、E、F的坐标。其中A、B、C按照逆时针顺序排列。,UVa 11178 Morleys Theorem,这题应该说很简单，在你看来，怎么解决？,以D点为例，D是BD，CD的交点，BD可由BC逆时针旋转三分之一ABC得到，同理可得到CD，然后求两直线交点即可。,UVALive 4757 Open-air shopping malls,题目意思：,平面上有n个圆，给定他们各自的圆心和半 径。保证任意两个圆不会互相重叠。现在 求一个大圆，它的圆心与某个给定圆的圆心重合，且对于每一个给定的圆，大圆至 少覆盖该圆面积的一半。请求得满足要求 的大圆的最小半径。,UVALive 4757 Open-air shopping malls,困难问题：直接求满足要求的最小半径,简单问题：已知一个半径，要判断它是否覆盖了给定圆的至少一半面积,性质：当圆心确定，若半径r的圆可以覆盖每一个给定圆至少一半的面积，那么对于半径Rr的圆，都可以覆盖至少一半的面积。,算法：二分答案,UVALive 4757 Open-air shopping malls,求两圆的相交面积：,UVALive 4757 Open-air shopping malls,算法流程,枚举圆心位置O,i,二分查找，求得对于当前圆心位置，满足要求的最小半径ri,记录上述所有r 中的最小值，并且输出结果。,时间复杂度 O(n,2,logn),UVALive 4838 Rotational Painting,题目意思：,有一块均匀厚度的多边形玻璃板，现在需要将它稳定地竖直放置，求有多少种不同的放置方法。题目描述中的图1和图2分别表示两个多边形的所有放置 方法，而图3 中的两种放法我们认为是不稳定的。,UVALive 4838 Rotational Painting,UVALive 4838 Rotational Painting,“稳定”的定义,多边形玻璃板的重心向水平面作垂线时，垂足落在支撑边所在的线段上（不包括线段端点）,对多边形支撑边的枚举,由于有可能出现凹多边形，因此可供选择的“支撑边”包括该多边形的凸包的所有边。,UVALive 4838 Rotational Painting,重心的求法,有向质量（回顾有向面积）,重心的求法,对于三顶点坐标为(x,1,y,1,)、(x,2,y,2,)及(x,3,y,3,)的三角形，其重心公式为：,x,0,=(x,1,+x,2,+x,3,)/3,y,0,=(y,1,+y,2,+y,3,)/3,多边形三角剖分,有向面积作为质量,（有向质量）,UVALive 4838 Rotational Painting,总结,求出多边形凸包；,求出多边形重心坐标；,由重心向每一条凸包边所在直线引垂线，通过垂足的位置判断该凸包边能否作为支撑边。并 在枚举过程中统计符合条件的支撑边(即摆放方法)的个数。,UVA 11168 Airport,题目意思：,给出平面上n（n10000）个点，找一条直线，是的所有的点都在直线的同侧（也可以在直线上），且使得各个点到直线的距离的和尽量小。,UVA 11168 Airport,怎么来枚举直线？,直线不可以穿过所有点组成的凸包，不难发现，选择凸包边所在的直线要比选择和凸包相离的直线更划算。,最直接的想法，枚举直线，再统计其他点到到该直线的距离，时间复杂度o(n,2,)。显然这个比现实。那怎么优化？,UVA 11168 Airport,点到直线的距离公式：,注意：所有的点都在直线的同一侧，我们可以由线性规划的知识得到，Ax+By+C的正负号是一致的，所以我们就可以将公式化解为：,所以只要预处理出所有x坐标的和y坐标之和，就可以在o(1)时间总距离。,UVA 11796 Dog Distance,题目意思：,甲和乙两条狗分别沿着一条折线的路径奔跑，两只狗的速度未知，但他们同时出发，同时到达终点，并且都是匀速奔跑。你的任务就是求出甲和乙在奔跑过程中最远距离和最近距离之差。,UVA 11796 Dog Distance,两个都是在动态变化的，这个看起了很难处理，怎么办？,简单例子：甲和乙的运动就是一条线段，那我们怎么处理？,由运动的相对性，我们可以假设甲是不动的，只有乙在运动，这样我们可以把他转化为：,点到线段的距离,UVA 11796 Dog Distance,有了简化版的分析，只需模拟整个过程就好。怎么模拟？,假设现在甲的位置在pa，刚经过编号为sa的拐点；乙的位置在pb，刚记过编号为sb的拐点，则我们只需要计算他俩谁先到达下一个观点就好，那么在这个时间点之前的问题就是我们刚才讨论过的“简化版”。求解完毕后更新最值，正好到达下一个拐点的时候还要更新sa和/或sb，然后继续模拟，时间复杂度o(n+m)。,HDU 4533 威威猫系列故事晒被子,题目意思：,在第一象限有n个平行于坐标轴的矩形被子，不同的被子可能有部分重叠，然后有q次询问，每次输入一个t，表示在（0，0）到（t，t）被水淹了，问你被子湿了的总面积是多少。,数据范围：,0 N=20000,1=x1 x2=200000,1=y1 y2=200000,1=x=20000,1=ti=200000（1=i=x）,HDU 4533 威威猫系列故事晒被子,对于这题的直接想法，也是最暴力的想法就是对于每一次询问都是算一遍，显然时间是不允许的！那怎么办，有没有高效的算法来实现呢？,看到题目，你的想法是？,HDU 4533 威威猫系列故事晒被子,考虑每次询问t,对于单一矩形的面积的计算方法,情况一：,计算如图矩形所被包含的面积可以用矩形面积STCFI-STJGI，而STCFI=(t-Fx)*(t-Fy),；,STJGI=(t-Gx)*(t-Gy),换句话说就是用T和矩形左下角的点形成的面积减去T和矩形右下角形成的矩形面积就是这个矩形被包含的面积！,HDU 4533 威威猫系列故事晒被子,当前矩形被包涵的面积是STLFI-STLEK。即T和矩形左下角点形成的面积减去T和矩形左上角点形成的矩形的面积！,情况二：,HDU 4533 威威猫系列故事晒被子,这时候的面积是EHGF的面积，但我们还想计算这个面积时和T有关。仿照前面的讨论，发现SEHGF不就是STLFI-STLEN-STMGI+STMHN么？,换句话描述，就是T和矩形左下角点形成的矩形面积减去T和矩形左上角点形成的矩形面积减去T和矩形右下角点形成的矩形面积加上T和矩形右上角点形成的矩形面积,情况三：,HDU 4533 威威猫系列故事晒被子,那么我们得到了如下算法：,输入询问t,sum=0,遍历所有矩形的四个顶点,如果该顶点在(0,0)-(t,t)的范围内,如果当前顶点是它所在矩形的左上角或右下角的点那么sum+=(t,t)和该点形成的矩形的面积,否则sum-=(t,t)和该点形成的矩形的面积,返回sum,HDU 4533 威威猫系列故事晒被子,对于这题目的数据来说时间复杂度肯定是不够的，我们要想办法优化它。,观察我们计算T和当前点形成的矩形面积时的方法：,假设当前点坐标是(x,y),那么S=(t-x)*(t-y),我们可以将上式展开：S=t*t-t(x+y)+xy,我们可不可以将上式分成的三部分分别求和呢？答案是可以的！,HDU 4533 威威猫系列故事晒被子,那么我们可以将所有矩形左下角和右上角的点分到一组a（因为它们和T形成的矩形面积都是做“加”运算），把左上角和右下角的点分到一组b（因为它们和T形成的矩形面积都是做“减”运算）,那么结果可以写成sigmaa中在(t,t)范围内的点和T形成的矩形面积-sigmab在(t,t)范围内的点和T形成的矩形面积,HDU 4533 威威猫系列故事晒被子,我们将a，b中的点分别按max(x,y)排序。,对于每次询问t，我们二分找到它在a,b中的位置n,m（即max(x,y)恰好不超过t的最大的下标，a,b都是从1开始编号）,答案不就是,Sum(Sa)-Sum(Sb),=sigmat*t-t*(x+y)+xy-sigmat*t-t*(x+y)+xy,=,sigma(t*t)-sigma(x+y)+sigma(xy)-sigma(t*t)-sigma(x+y)+sigma(xy),HDU 4533 威威猫系列故事晒被子,总结：,（1）,检查所有矩形的四个顶点,，,如果是左下角或是右上角的点那么放到a的末尾,，,否则放到b的末尾,。,（2）,将a,b中的所有点按max(x,y)排序,（3）,定义suma,sumb表示a、b的点中下标1到下标i的所有点的x+y和定义suma_mul,sumb_mul表示a、b的点中下标1到下标i的所有点的x*y和,，,循环 i=1 到 2*N,sumai=sumai-1+ai.x+ai.y,sumbi=sumbi-1+bi.x+bi.y,suma_muli=suma_muli-1+ai.x*ai.y,sumb_muli=sumb_muli-1+bi.y*bi.y,（4）,对于每次询问t,，,二分找到在a,b中max(x,y)恰好不超过t的下标n,m,，,输出答案(t*t*n-t*suman+suma_mumn)-(t*t*m-t*sumbm+sumb_mulm),POJ 1066 Treasure Hunt,题目意思：,一个正方形围墙内有一些交错的内墙，内墙的端点都在正方形上，在正方形内部有一个点，求从正方形外到这个点的最少要走的门数，门只能是线段的中点。,POJ 1066 Treasure Hun,t,从一个点到终点不可能“绕过”围墙，只能穿过去，所以门是否开在中点是无所谓的，只要求四周线段中点到终点的线段与墙的最少交点个数即可。,看似相当的复杂，你的着手点在哪里？,更进一步，实际上，只需判断四周围墙的所有点与终点的连线与内墙的最少交点加一即可,课堂寄语,有志者自有千计万计，无志者只感千难万难。,