[计算几何在程序设计竞赛中的应用.ppt

计算几何在程序设计竞赛中的应用 预备知识(I) 差积： 预备知识(II) 差积应用(1)：判断两条线段是否相交 预备知识(III) 特殊情况： 预备知识(VI) 为解决上述问题，我们引入点积： 预备知识(V) 设dot(a,b,c) 返回a,b.a,c的值。我们来看dot(a,b,c)值与c在ab上投影c’的关系. 基本问题举例(Ⅰ) 1.位置 (左右)判断 基本问题举例(Ⅰ) 基本思路： 基本问题举例(Ⅰ) 代码： 基本问题举例（Ⅱ） 2.求交点（ZJU1460） 问题描述：用刀切1000*1000的方形蛋糕，问切割若干刀之后，蛋糕被分为多少块，假设： 蛋糕顶点坐标为(0,0)(0,1000)(1000,1000)(1000,0) 切割刀数不超过8 切割后每一块蛋糕的边长不小于1 切割线和蛋糕边界有两个交点 基本问题举例（Ⅱ） 基本思路 假设平面上已经被m条直线切割成了n块，那么再增加一条直线增加的块数等于增加的交点数加1。 基本问题举例（Ⅱ） 相关算法 根据已知两点坐标，求过这两点的直线解析方程： a*x+b*y+c = 0 (a = 0) 基本问题举例（Ⅱ） 相关算法 判断两线段是否相交，如果相交则求出交点 相交用叉积cross(a,b,c)*cross(a,b,d)0 cross(c,d,a)*cross(c,d,b)0)判断（注意表示越界） 求交点 基本问题举例（Ⅱ） 特殊情况 切割线和边界或者以前的切割线重合（排除） 重复交点（只计算1次） 在边界相交（不增加交点） 基本问题举例（Ⅱ） 代码（主程序） 基本问题举例(Ⅲ) 3.求多边形的面积。 前面已经讲过，两向量的叉积的几何意义是以这两个向量为邻边的平行四边形的有向面积，我们可以利用这一点来求简单多边形的面积。 所谓简单多边形就是任何不相邻的两条边都没有交点，包括凸多边形和凹多边形。 基本问题举例(Ⅲ) 求下面多边形的面积，已知个顶点的坐标。 基本问题举例(Ⅳ) 4.求凸包 定义：直观地讲，对于一个平面点集或者一个 多边形，它的凸包指的是包含它的最小凸 图形或最小凸区域。 基本问题举例(Ⅳ) Graham-Scan算法(了解Gift-Wrapping算法 ) 试探性凸包 我们尝试从p1(最低点，一定属于凸包)出发，沿着多边形顶点逆时针的顺序，试探性的增长凸包.显然，一个点如果属于凸包，那么它到达下一个点一定需要左转，否则，该点一定不属于凸包。 基本问题举例(Ⅳ) 算法总结： 基本问题举例(Ⅳ) 3.伪代码： push(p1);push(p2); i=3; while i=n do if pi 在栈顶边pt-1pt左手方向 then push(pi) 并且i++； else pop(); 附加问题(需要离散化问题) 例：zju1128 问题描述：一些已知右下顶点和左上顶点坐标的矩形，这些矩形可能部分重叠，求它们所占的实际面积。例如： 附加问题(需要离散化问题) 方案一、 把矩形映射到数组M[ ][ ]中，如果某矩形的位置为（x1，y1）（x2，y2）则M[i][j]=1（其中x1=i=x2,y1=j=y2）。但是，如果坐标值离散程度很大或者非整型，此方案就不可行。 附加问题(需要离散化问题) 方案三——离散化 附加问题(需要离散化问题) 代码 #includeiostream using namespace std; double x[200],y[200],in[100][4]; bool xy[200][200]; double N=0.000001; int n_map; void input(); void solve(); double cacu(); 附加问题(需要离散化问题) int main(){ while(cinn_map n_map != 0) { input(); sort(x,x+2*n_map); sort(y,y+2*n_map); memset(xy,0,sizeof(xy)); solve(); double sum=cacu(); coutsumendl; } return 0; } 附加问题(需要离散化问题) void input(){ for(int i = 0,k=0 ; i n_map ; i++) { cinin[i][0]in[i][1]in[i][2]in[i][3]; x[k] = in[i][0]; y[k] = in[i][1]; k++; x[k] = in[i][2]; y[k] = in[i][3]; k++