《计算几何专题.ppt》由会员分享，可在线阅读，更多相关《计算几何专题.ppt（84页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
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多边形面积凸多边形的三角形剖分很自
18、然地，我们会想到以 P1为扇面中心，连接P1Pi就得到N-2个三角形，由于凸性，保证这些三角形全在多边形内，那么，这个凸多边形的有向面积：A=sigma(Ai)(i=1N-2)P1P2P3P4P5P6A1A2A3A4多边形面积凹多边形的面积P1P4P3P2多边形面积任意点为扇心的三角形剖分：任意点为扇心的三角形剖分：我们能把多边形分成N-2个三角形，为什么不能分成N个三角形呢？比如，以多边形内部的一个点为扇心，就可以把多边形剖分成 N个三角形。P1P2P6P5P4P3多边形面积前面的三角剖分显然对于多边形内部任意一点都是合适的！（把分割点放在原点？）我们可以得到：A=sigma(Ai)（i=1
19、N）即：A=sigma /2 （i=1N）Xi X0 Yi Y0X(i+1)X0 Y(i+1)Y0点在多边形内的判定方法一：射线法从判定点任意引一条射线，如果和边界的交点是奇数次，说明点在多边形内，如果交点为偶数个，点在多边形外。在多边形上需另外判断。方法二：转角法计算多边形每条边的转角的和，如果为360度，则点在多边形内，如果为0度，则在多边形外，如果为180度则点在多边形上（也适合非简单多边形）。点在多边形内的判定如果按照上面的定义实现，需要计算大量的反三角函数，不仅速度慢，而且容易产生精度误差。我们一般假设一条向右的射线，统计多边形穿过这条射线的正反次数，把这个数记为绕数wn（Wingi
20、ng Number），逆时针穿过是wn+，顺时针穿过wn-。注意在程序现实的时候，判断是否穿过，以及穿过方向时，需要用叉积判断输入点在边的左边还是右边。点在多边形内的判定int isPointInPolygon(Point p,Polyon poly)int w=0,n=v.size();for(int i=0;i0&d10)wn+;if(k0&d20)wn-;if(wn!=0)return 1;/内部return 0;/外部凸包顾名思义，凸包就是把给定点包围在内部、面积最小的图多边形，它在计算几何里有着极其重要的作用。凸包在网上可以找到很多关于凸包的算法的资料，这里我们简单叙述一下基于水平序
21、的Andrew算法。首先把所有的点按照x从小到大排列（x相同，按y从小到大排列），删除重复点得到序列p1，p2，然后把p1，p2放到凸包中，从p3开始，当新点在凸包“前进”方向的左边时继续前进，否则依次删除最近加入凸包的点，直到新点在左边。凸包如图，新点p18在向量p10p15（即当前前进方向）的右边，因此需要从凸包上删除p15和p10，让p8的下一个点为p18。重复上述过程，直到碰到最右边的点pn，就求得了“下凸包”。然后反过来从pn开始再做一遍，求出“上凸包”，合并起来就是完整的凸包了。p5p8p10p15p18p5p8p10p15p18凸包int ConvexHull(Point*p,i
22、nt n,Point*ch)sort(p,p+n);int m=0;for(int i=0;i1&Cross(chm-1-chm-2,pi-chm-1)=0;i-)while(mk&Cross(chm-1-chm-2,pi-chm-1)r的圆，都可以覆盖至少一半的面积。算法：二分答案 UVALive 4757 Open-air shopping malls求两圆的相交面积：UVALive 4757 Open-air shopping malls算法流程 枚举圆心位置Oi 二分查找，求得对于当前圆心位置，满足要求的最小半径ri 记录上述所有r 中的最小值，并且输出结果。时间复杂度 O(n2log
23、n)UVALive 4838 Rotational Painting题目意思：题目意思：有一块均匀厚度的多边形玻璃板，现在需要将它稳定地竖直放置，求有多少种不同的放置方法。题目描述中的图1和图2分别表示两个多边形的所有放置 方法，而图3 中的两种放法我们认为是不稳定的。UVALive 4838 Rotational Painting UVALive 4838 Rotational Painting“稳定”的定义 多边形玻璃板的重心向水平面作垂线时，垂足落在支撑边所在的线段上（不包括线段端点）对多边形支撑边的枚举 由于有可能出现凹多边形，因此可供选择的“支撑边”包括该多边形的凸包的所有边。UVA
24、Live 4838 Rotational Painting重心的求法 有向质量（回顾有向面积）重心的求法 对于三顶点坐标为(x1,y1)、(x2,y2)及(x3,y3)的三角形，其重心公式为：x0=(x1+x2+x3)/3 y0=(y1+y2+y3)/3 多边形三角剖分 有向面积作为质量 （有向质量）UVALive 4838 Rotational Painting总结 求出多边形凸包；求出多边形重心坐标；由重心向每一条凸包边所在直线引垂线，通过垂足的位置判断该凸包边能否作为支撑边。并 在枚举过程中统计符合条件的支撑边(即摆放方法)的个数。UVA 11168 Airport题目意思：题目意思：给
25、出平面上n（n10000）个点，找一条直线，是的所有的点都在直线的同侧（也可以在直线上），且使得各个点到直线的距离的和尽量小。UVA 11168 Airport怎么来枚举直线？直线不可以穿过所有点组成的凸包，不难发现，选择凸包边所在的直线要比选择和凸包相离的直线更划算。最直接的想法，枚举直线，再统计其他点到到该直线的距离，时间复杂度o(n2)。显然这个比现实。那怎么优化？UVA 11168 Airport点到直线的距离公式：注意：所有的点都在直线的同一侧，我们可以由线性规划的知识得到，Ax+By+C的正负号是一致的，所以我们就可以将公式化解为：所以只要预处理出所有x坐标的和y坐标之和，就可以在
26、o(1)时间总距离。UVA 11796 Dog Distance题目意思：题目意思：甲和乙两条狗分别沿着一条折线的路径奔跑，两只狗的速度未知，但他们同时出发，同时到达终点，并且都是匀速奔跑。你的任务就是求出甲和乙在奔跑过程中最远距离和最近距离之差。UVA 11796 Dog Distance两个都是在动态变化的，这个看起了很难处理，怎么办？简单例子：甲和乙的运动就是一条线段，那我们怎么处理？由运动的相对性，我们可以假设甲是不动的，只有乙在运动，这样我们可以把他转化为：点到线段的距离 UVA 11796 Dog Distance有了简化版的分析，只需模拟整个过程就好。怎么模拟？假设现在甲的位置在
27、pa，刚经过编号为sa的拐点；乙的位置在pb，刚记过编号为sb的拐点，则我们只需要计算他俩谁先到达下一个观点就好，那么在这个时间点之前的问题就是我们刚才讨论过的“简化版”。求解完毕后更新最值，正好到达下一个拐点的时候还要更新sa和/或sb，然后继续模拟，时间复杂度o(n+m)。HDU 4533 威威猫系列故事晒被子题目意思：题目意思：在第一象限有n个平行于坐标轴的矩形被子，不同的被子可能有部分重叠，然后有q次询问，每次输入一个t，表示在（0，0）到（t，t）被水淹了，问你被子湿了的总面积是多少。数据范围：0 N=200001=x1 x2=2000001=y1 y2=2000001=x=2000
28、01=ti=200000（1=i=x）HDU 4533 威威猫系列故事晒被子对于这题的直接想法，也是最暴力的想法就是对于每一次询问都是算一遍，显然时间是不允许的！那怎么办，有没有高效的算法来实现呢？看到题目，你的想法是？HDU 4533 威威猫系列故事晒被子考虑每次询问t,对于单一矩形的面积的计算方法情况一：计算如图矩形所被包含计算如图矩形所被包含的面积可以用矩形面积的面积可以用矩形面积STCFI-STJGI，而，而STCFI=(t-Fx)*(t-Fy)；STJGI=(t-Gx)*(t-Gy)换句话说就是用换句话说就是用T和矩形和矩形左下角的点形成的面积左下角的点形成的面积减去减去T和矩形右下
29、角形成和矩形右下角形成的矩形面积的矩形面积就是这个矩就是这个矩形被包含的面积！形被包含的面积！HDU 4533 威威猫系列故事晒被子当前矩形被包涵当前矩形被包涵的面积是的面积是STLFI-STLEK。即。即T和矩形左下角点和矩形左下角点形成的面积形成的面积减去减去T和矩形左上角和矩形左上角点形成的矩形的点形成的矩形的面积面积！情况二：HDU 4533 威威猫系列故事晒被子这时候的面积是这时候的面积是EHGF的面的面积，但我们还想计算这个面积，但我们还想计算这个面积时和积时和T有关。仿照前面的有关。仿照前面的讨论，发现讨论，发现SEHGF不就是不就是STLFI-STLEN-STMGI+STMHN
30、么？么？换句话描述，就是换句话描述，就是T和矩形和矩形左下角点形成的矩形面积左下角点形成的矩形面积减去减去T和矩形左上角点形成和矩形左上角点形成的矩形面积的矩形面积减去减去T和矩形和矩形右下角点形成的矩形面积右下角点形成的矩形面积加上加上T和矩形右上角点形成和矩形右上角点形成的矩形面积的矩形面积情况三：HDU 4533 威威猫系列故事晒被子那么我们得到了如下算法：输入询问tsum=0遍历所有矩形的四个顶点 如果该顶点在(0,0)-(t,t)的范围内 如果当前顶点是它所在矩形的左上角或右下角的点那么sum+=(t,t)和该点形成的矩形的面积 否则sum-=(t,t)和该点形成的矩形的面积返回su
31、m HDU 4533 威威猫系列故事晒被子对于这题目的数据来说时间复杂度肯定是对于这题目的数据来说时间复杂度肯定是不够的，我们要想办法优化它。不够的，我们要想办法优化它。观察我们计算T和当前点形成的矩形面积时的方法：假设当前点坐标是(x,y)那么S=(t-x)*(t-y)我们可以将上式展开：S=t*t-t(x+y)+xy我们可不可以将上式分成的三部分分别求和呢？答案是可以的！HDU 4533 威威猫系列故事晒被子那么我们可以将所有矩形左下角和右上角的点分到一组a（因为它们和T形成的矩形面积都是做“加”运算），把左上角和右下角的点分到一组b（因为它们和T形成的矩形面积都是做“减”运算）那么结果可
32、以写成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 威威猫系列故
33、事晒被子总结：（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,
34、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 Hunt从一个点到终点不可能“绕过”围墙，只能穿过去，所以门是否开在中点是无所谓的，只要求四周线段中点到终点的线段与墙的最少交点个数即可。看似相当的复杂，你的着手点在哪里？更进一步，实际上，只需判断四周围墙的所有点与终点的连线与内墙的最少交点加一即可课堂寄语有志者自有千计万计，无志者只感千难万难。