已阅读5页,还剩115页未读, 继续免费阅读
版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
1 目录目录 一一几何几何.4 1.1 注意.4 1.2 几何公式.4 1.3 多边形.6 1.4 多边形切割.9 1.5 浮点函数.10 1.6 面积.15 1.7 球面.16 1.8 三角形.17 1.9 三维几何.19 1.10 凸包.27 1.11 网格.28 1.12 圆.28 1.13 整数函数.30 二组合二组合.33 2.1 组合公式.33 2.2 排列组合生成 .33 2.3 生成GRAY码 .35 2.4 置换(POLYA) .35 2.5 字典序全排列 .36 2.6 字典序组合.36 三结构三结构.37 3.1 并查集.37 3.2 堆.38 3.3 线段树.39 3.4 子段和.44 3.5 子阵和.45 四数论四数论.45 4.1 阶乘最后非 0 位 .45 4.2 模线性方程组 .46 4.3 素数.47 4.4 欧拉函数.49 4.5 定积分计算(ROMBERG).49 4.6 多项式求根(牛顿法).51 4.7 周期性方程(追赶法).52 五图论五图论.53 5.1NP 搜索.53 2 5.1.1 最大团.53 5.1.2 最大团(n0?(x):-(x)eps?1:(x)-eps?2:0) struct pointdouble x,y; struct linepoint a,b; double xmult(point p1,point p2,point p0) return (p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y); 7 /判定凸多边形,顶点按顺时针或逆时针给出,允许相邻边共线 int is_convex(int n,point* p) int i,s3=1,1,1; for (i=0;ini+) s_sign(xmult(p(i+1)%n,p(i+2)%n,pi)=0; return s1|s2; /判定凸多边形,顶点按顺时针或逆时针给出,不允许相邻边共线 int is_convex_v2(int n,point* p) int i,s3=1,1,1; for (i=0;ini+) s_sign(xmult(p(i+1)%n,p(i+2)%n,pi)=0; return s0 /判点在凸多边形内或多边形边上,顶点按顺时针或逆时针给出 int inside_convex(point q,int n,point* p) int i,s3=1,1,1; for (i=0;ini+) s_sign(xmult(p(i+1)%n,q,pi)=0; return s1|s2; /判点在凸多边形内,顶点按顺时针或逆时针给出,在多边形边上返回 0 int inside_convex_v2(point q,int n,point* p) int i,s3=1,1,1; for (i=0;ini+) s_sign(xmult(p(i+1)%n,q,pi)=0; return s0 /判点在任意多边形内,顶点按顺时针或逆时针给出 /on_edge 表示点在多边形边上时的返回值,offset 为多边形坐标上限 int inside_polygon(point q,int n,point* p,int on_edge=1) point q2; int i=0,count; while (in) for (count=i=0,q2.x=rand()+offset,q2.y=rand()+offset;in;i+) if (zero(xmult(q,pi,p(i+1)%n) 8 else if (zero(xmult(q,q2,pi) break; else if (xmult(q,pi,q2)*xmult(q,p(i+1)%n,q2)- eps return count inline int opposite_side(point p1,point p2,point l1,point l2) return xmult(l1,p1,l2)*xmult(l1,p2,l2)-eps; inline int dot_online_in(point p,point l1,point l2) return zero(xmult(p,l1,l2) /判线段在任意多边形内,顶点按顺时针或逆时针给出,与边界相交返回 1 int inside_polygon(point l1,point l2,int n,point* p) point tMAXN,tt; int i,j,k=0; if (!inside_polygon(l1,n,p)|!inside_polygon(l2,n,p) return 0; for (i=0;in;i+) if (opposite_side(l1,l2,pi,p(i+1)%n) else if (dot_online_in(l1,pi,p(i+1)%n) tk+=l1; else if (dot_online_in(l2,pi,p(i+1)%n) tk+=l2; else if (dot_online_in(pi,l1,l2) tk+=pi; for (i=0;ik;i+) for (j=i+1;jeps) ret.x/=t1,ret.y/=t1; return ret; 1.4 多边形切割多边形切割 /多边形切割 /可用于半平面交 #define MAXN 100 #define eps 1e-8 #define zero(x) (x)0?(x):-(x)eps; point intersection(point u1,point u2,point v1,point v2) point ret=u1; double t=(u1.x-v1.x)*(v1.y-v2.y)-(u1.y-v1.y)*(v1.x-v2.x) /(u1.x-u2.x)*(v1.y-v2
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 2024年农副产品购销结合合同示范文本(二篇)
- 2024年简单私人购房合同参考范文(二篇)
- 2024年防水工程施工合同参考样本(四篇)
- 2024年私家车辆出售合同(二篇)
- 2024年公司销售合同标准样本(二篇)
- 2024年一线城市房屋出租居间合同范本(二篇)
- 2024年建设工程技术咨询合同常用版(三篇)
- 2024年房产赠与协议标准范文(5篇)
- 2024年理发店学徒合同协议范本(二篇)
- 陕西省榆林市高新区2023-2024学年七年级下学期期中考试语文试题
- QCT 388-2023 碗形塞片 (正式版)
- 地热科学探井-福深热1井项目 环评报告
- 初中物理中考模拟试题与答案解析(共三套)
- 踝关节及足部手术护理课件
- 数控车床培训课件
- ISO9001 ISO14001 QC080000 ISO45001质量环境有害物质职业健康安全四体系内部审核全套通用资料
- 血友病的家庭护理
- 推广漫画活动方案策划
- 打造小学高效课堂的经验和方法
- 毒蘑菇健康知识讲座
- 地下室消防安全管理要点课件
评论
0/150
提交评论