logo资料库

ACM计算几何基础模板，杭电老学长精心整理.pdf

发布时间：2022-06-10 发布人：admin 分类：说明书 资料大小：0.79M 资料格式：pdf 举报 版权申诉
第1页 / 共34页
第2页 / 共34页
第3页 / 共34页
第4页 / 共34页
第5页 / 共34页
第6页 / 共34页
第7页 / 共34页
第8页 / 共34页
资料共34页，剩余部分请下载后查看
          计算几何 计算几何基础 0.公式 三角形: 1. 半周长  2. 面积  3. 中线  4. 角平分线  5. 高线  6. 内切圆半径  7. 外接圆半径  四边形: D1,D2为对角线,M对角线中点连线,A为对角线夹角 ,P为半周长    (以下对圆的内接四边形) 1.  2.  3.  4.  正n边形: R为外接圆半径,r为内切圆半径 1. 中心角  2. 内角  3. 边长  4. 面积  圆: 1. 弧长 
    2. 弦长  3. 弓形高  4. 扇形面积  5. 弓形面积  棱柱: 1. 体积  2. 侧面积  3. 全面积  棱锥: ,A为底面积,h为高 ,l为棱长,p为直截面周长 1. 体积  A为底面积,h为高   ,l为斜高,p为底面周长 ,A1.A2为上下底面积,h为高   为上下底面周长,l为斜高 (以下对正棱锥) 2. 侧面积  3. 全面积  棱台: 1. 体积  (以下为正棱台) 2. 侧面积  3. 全面积  圆柱: 1. 侧面积  2. 全面积  3. 体积  圆锥: 1. 母线  2. 侧面积  3. 全面积  4. 体积  圆台: 1. 母线  2. 侧面积  3. 全面积  4. 体积 
    球: 1. 全面积  2. 体积  球台: 1. 侧面积  2. 全面积  3. 体积  球扇形: 1. 全面积  2. 体积  ,h为球冠高,r0为球冠底面半径 1.常量、基础函数 #include #include #include using namespace std; const double pi = 3.1415926535898; const double eps = 1e-8; inline int fcmp(double x,double y) //浮点比较 { if(fabs(x-y) < eps) return 0; else return x > y ? 1 : -1; } inline double sqr(double x) //浮点平方 { return x * x; } inline double Sqrt(double x) { return x <= 0 ? 0 : sqrt(x); } inline int abs(int x) { return x >= 0 ? x : -x; } int main() { double x; int fx = floor(x); //向下取整
    int cx = ceil(x); //向上取整 int rx = round(x); //四舍五入 } 2.二维点、向量 2.1 二维点类 struct Point { double x, y, ang; Point(){} Point(double a, double b): x(a), y(b) {} friend Point operator + (const Point &a, const Point &b){ return Point(a.x + b.x, a.y + b.y); } friend Point operator - (const Point &a, const Point &b){ return Point(a.x - b.x, a.y - b.y); } friend bool operator == (const Point &a, const Point &b){ return fcmp(a.x,b.x) == 0 && fcmp(a.y,b.y) == 0; } friend Point operator * (const Point &a, const double &b){ return Point(a.x * b, a.y * b); } friend Point operator * (const double a,const Point &b){ return Point(a * b.x, a * b.y); } friend Point operator / (const Point &a, const double &b){ return Point(a.x / b, a.y / b); } friend bool operator < (const Point &a,const Point &b){ if(a.x == b.x) return a.y < b.y; return a.x < b.x; } friend double norm(const Point &a){ return sqrt(sqr(a.x) + sqr(a.y)); } void calcangle() {ang = atan2(y,x);} }; 2.2 向量
    既有大小又有方向的量叫向量 通常用坐标表示 鉴于以上两点，向量可以用二维点类表示。   2.2.1向量运算 1. 内积 向量夹角为锐角，内积为正 向量夹角为钝角，内积为负 向量夹角为直角，内积为0 inline double dot(const Point &a,const Point &b) //内积 { return a.x * b.x + a.y * b.y; } 2. 叉积 根据右手定则 若 若 若  B在A的顺时针方向  B与A共线  B在A的逆时针方向 inline double det(const Point &a,const Point &b) //外积 { return a.x * b.y - a.y * b.x; } 3.两点间距离(向量长度) inline double dist(const Point &a,const Point &b) //两点间距离 { return (a - b).norm(); } 4.两向量夹角(弧度)
    inline double angle(const Point &a,const Point &b) //向量夹角 { return acos(dot(a,b) / norm(a) / norm(b)); } 5.向量绕原点逆时针旋转A(弧度) inline Point rotate_point(const Point &p,double A) //计算点p绕原点逆时针旋转 A(弧度) { return Point(p.x * cos(A) - p.y * sin(A),p.x * sin(A) - p.y * cos(A)); } 6.计算两向量构成的平行四边形有向面积 inline double area2(const Point a,const Point &b) //计算两向量构成的有向面积 { return det(a,b); } 2.3 点与线 2.3.1 直线线段类 struct Line { Point s, t; double ang; //直线极角 Line(){}; Line(Point a,Point b) : s(a) , t(b) {} Line(Point p,double ang) //根据一个点和一个角(弧度制，0 <= ang < pi) 确定直线 { s = p; if(sgn(ang - pi / 2) == 0) t = (s + Point(0,1)); else t = s + Point(1,tan(ang)); } Line(double a,double b,double c) // ax + by + c = 0 { if(sgn(a) == 0){s = Point(0,-c/b); t = Point(1,-c/b);} else if(sgn(b) == 0){s = Point(-c/a,0); t = Point(-c/a,1);} else{s = Point(0,-c/b); t = Point(1,(-c-a)/b);}
    } void calcangle() {ang = atan2((t - s).y, (t - s).x);} //计算直线极角 }; 2.3.2 点与线关系计算 1.点到直线距离 inline double dis_point_line(const Point &p,const Point s,const Point &t) //计算点到直线距离 { return fabs(det(s-p,t-p) / dist(s,t)); } 2. 点到线段距离 若投影不在线段内，则距离为点到端点距离 inline double dis_point_segment(const Point &p,const Point &s,const Point &t) //计算点到线段距离 { if(sgn(dot(p-s,t-s)) < 0) return norm(p-s); if(sgn(dot(p-t,s-t)) < 0) return norm(p-t); return fabs(det(s-p,t-p) / dist(s,t)); } 3.判断点相对直线的方向 inline int point_on_line(const Point &p,const Point &s,const Point &t) //判断p位于直线的哪一边 { //位于s的逆时针方向返回-1 //位于s的顺时针方向返回1 //在直线上返回0 return sgn(det(p-s,t-s)); } 4.判断点p是否位于线段上(包括端点) inline bool point_on_segment(const Point &p,const Point &s,const Point & t) { return (sgn(det(p-s,t-s)) == 0 && sgn(dot(p-s,p-t)) <= 0); }
    5.计算点p于直线的投影,计算两点中垂线 定比分点 inline Point point_proj_line(const Point &p,const Point &s,const Point & t) { double r = dot((t-s),(p-s)) / dot(t-s,t-s); return s + r * (t - s); } inline Line get_mid_line(const Point &a, const Point &b) //计算线段ab的中垂 线 { Point mid = (a + b) / 2; Point tp = b-a; return Line(mid,mid+Point(-tp.y,tp.x)); } 6.判断两直线是否平行 若平行，两直线向量叉乘结果为0 inline bool parallel(const Line &A,const Line &B) //判断两直线是否平行 { return !sgn(det(A.s-A.t,B.s-B.t)); } 7.计算两直线交点，若存在，保存在res中 用到了定比分点公式的坐标形式
    分享到：
    赞 收藏

    相关推荐

    资料库

    课程资源

    共收录17145份资料，累计13个分类，关注成员有19位，主要包括：PHP,网络管理,网页制作,Java,.Net,数据库,3G/移动开发,C/C++,游戏开发,嵌入式,讲义,软件测试,专业指导

    热门标签

    PHP 网络管理 网页制作 Java .Net 数据库 3G/移动开发 C/C++ 游戏开发 嵌入式 讲义 软件测试 专业指导

    最新资料