几何公式浙大.doc

Zhejiang UniversityICPC Team Routine Library 1、 几何 51.1 注意 51.2 几何公式 51.3 多边形 71.4 多边形切割 101.5 浮点函数 111.6 面积 161.7 球面 171.8 三角形 181.9 三维几何 201.10 凸包 271.11 网格 291.12 圆 291.13 整数函数 312、组合 342.1 组合公式 342.2 排列组合生成 342.3 生成gray码 362.4 置换(polya) 362.5 字典序全排列 372.6 字典序组合 373、结构 383.1 并查集 383.2 堆 393.3 线段树 403.4 子段和 453.5 子阵和 454、数论 464.1 阶乘最后非0位 464.2 模线性方程组 474.3 素数 484.4 欧拉函数 495、数值计算 505.1 定积分计算(Romberg) 505.2 多项式求根(牛顿法) 525.3 周期性方程(追赶法) 536、图论—NP搜索 546.1 最大团 546.2 最大团(n<64)(faster) 557、图论—连通性 577.1 无向图关键点(dfs邻接阵) 577.2 无向图关键边(dfs邻接阵) 587.3 无向图的块(bfs邻接阵) 597.4 无向图连通分支(dfs/bfs邻接阵) 607.5 有向图强连通分支(dfs/bfs邻接阵) 617.6 有向图最小点基(邻接阵) 628、图论—匹配 638.1 二分图最大匹配(hungary邻接表) 638.2 二分图最大匹配(hungary邻接阵) 648.3 二分图最大匹配(hungary正向表) 648.4二分图最佳匹配(kuhn_munkras邻接阵) 658.5 一般图匹配(邻接表) 668.6 一般图匹配(邻接阵) 678.7 一般图匹配(正向表) 679、图论—网络流 689.1 最大流(邻接阵) 689.2 上下界最大流(邻接阵) 699.3 上下界最小流(邻接阵) 709.4 最大流无流量(邻接阵) 719.5 最小费用最大流(邻接阵) 7110、图论—应用 7210.1 欧拉回路(邻接阵) 7210.2 树的前序表转化 7310.3 树的优化算法 7410.4 拓扑排序(邻接阵) 7510.5 最佳边割集 7610.6 最佳点割集 7710.7 最小边割集 7810.8 最小点割集 7910.9 最小路径覆盖 8111、图论—支撑树 8111.1 最小生成树(kruskal邻接表) 8111.2 最小生成树(kruskal正向表) 8311.3 最小生成树(prim+binary_heap邻接表) 8411.4 最小生成树(prim+binary_heap正向表) 8511.5 最小生成树(prim+mapped_heap邻接表) 8611.6 最小生成树(prim+mapped_heap正向表) 8811.7 最小生成树(prim邻接阵) 8911.8 最小树形图(邻接阵) 8912、图论—最短路径 9112.1 最短路径(单源bellman_ford邻接阵) 9112.2 最短路径(单源dijkstra+bfs邻接表) 9112.3 最短路径(单源dijkstra+bfs正向表) 9212.4 最短路径(单源dijkstra+binary_heap邻接表) 9312.5 最短路径(单源dijkstra+binary_heap正向表) 9412.6 最短路径(单源dijkstra+mapped_heap邻接表) 9512.7 最短路径(单源dijkstra+mapped_heap正向表) 9612.8 最短路径(单源dijkstra邻接阵) 9712.9 最短路径(多源floyd_warshall邻接阵) 9813、应用 9813.1 Joseph问题 9813.2 N皇后构造解 9913.3 布尔母函数 10013.4 第k元素 10013.5 幻方构造 10113.6 模式匹配(kmp) 10213.7 逆序对数 10313.8 字符串最小表示 10313.9 最长公共单调子序列 10413.10 最长子序列 10513.11 最大子串匹配 10613.12 最大子段和 10713.13 最大子阵和 10714、其它 10814.1 大数(只能处理正数) 10814.2 分数 11414.3 矩阵 11614.4 线性方程组 11814.5 线性相关 12014.6 日期 1201、 几何1.1 注意1. 注意舍入方式(0.5的舍入方向);防止输出-0.2. 几何题注意多测试不对称数据.3. 整数几何注意xmult和dmult是否会出界; 符点几何注意eps的使用.4. 避免使用斜率;注意除数是否会为0.5. 公式一定要化简后再代入.6. 判断同一个2*PI域内两角度差应该是 abs(a1-a2)pi+pi-beta; 相等应该是 abs(a1-a2)pi+pi-eps;7. 需要的话尽量使用atan2,注意:atan2(0,0)=0, atan2(1,0)=pi/2,atan2(-1,0)=-pi/2,atan2(0,1)=0,atan2(0,-1)=pi.8. cross product = |u|*|v|*sin(a) dot product = |u|*|v|*cos(a)9. (P1-P0)x(P2-P0)结果的意义: 正: 在顺时针(0,pi)内 负: 在逆时针(0,pi)内 0 : ,共线,夹角为0或pi10. 误差限缺省使用1e-8!1.2 几何公式三角形:1. 半周长 P=(a+b+c)/22. 面积 S=aHa/2=absin(C)/2=sqrt(P(P-a)(P-b)(P-c))3. 中线 Ma=sqrt(2(b^2+c^2)-a^2)/2=sqrt(b^2+c^2+2bccos(A))/24. 角平分线 Ta=sqrt(bc((b+c)^2-a^2))/(b+c)=2bccos(A/2)/(b+c)5. 高线 Ha=bsin(C)=csin(B)=sqrt(b^2-((a^2+b^2-c^2)/(2a))^2)6. 内切圆半径 r=S/P=asin(B/2)sin(C/2)/sin((B+C)/2) =4Rsin(A/2)sin(B/2)sin(C/2)=sqrt((P-a)(P-b)(P-c)/P) =Ptan(A/2)tan(B/2)tan(C/2)7. 外接圆半径 R=abc/(4S)=a/(2sin(A))=b/(2sin(B))=c/(2sin(C))四边形:D1,D2为对角线,M对角线中点连线,A为对角线夹角1. a^2+b^2+c^2+d^2=D1^2+D2^2+4M^22. S=D1D2sin(A)/2(以下对圆的内接四边形)3. ac+bd=D1D24. S=sqrt((P-a)(P-b)(P-c)(P-d)),P为半周长正n边形:R为外接圆半径,r为内切圆半径1. 中心角 A=2PI/n2. 内角 C=(n-2)PI/n3. 边长 a=2sqrt(R^2-r^2)=2Rsin(A/2)=2rtan(A/2)4. 面积 S=nar/2=nr^2tan(A/2)=nR^2sin(A)/2=na^2/(4tan(A/2))圆:1. 弧长 l=rA2. 弦长 a=2sqrt(2hr-h^2)=2rsin(A/2)3. 弓形高 h=r-sqrt(r^2-a^2/4)=r(1-cos(A/2))=atan(A/4)/24. 扇形面积 S1=rl/2=r^2A/25. 弓形面积 S2=(rl-a(r-h))/2=r^2(A-sin(A))/2棱柱:1. 体积 V=Ah,A为底面积,h为高2. 侧面积 S=lp,l为棱长,p为直截面周长3. 全面积 T=S+2A棱锥:1. 体积 V=Ah/3,A为底面积,h为高(以下对正棱锥)2. 侧面积 S=lp/2,l为斜高,p为底面周长3. 全面积 T=S+A棱台:1. 体积 V=(A1+A2+sqrt(A1A2))h/3,A1.A2为上下底面积,h为高(以下为正棱台)2. 侧面积 S=(p1+p2)l/2,p1.p2为上下底面周长,l为斜高3. 全面积 T=S+A1+A2圆柱:1. 侧面积 S=2PIrh2. 全面积 T=2PIr(h+r)3. 体积 V=PIr^2h圆锥:1. 母线 l=sqrt(h^2+r^2)2. 侧面积 S=PIrl3. 全面积 T=PIr(l+r)4. 体积 V=PIr^2h/3圆台:1. 母线 l=sqrt(h^2+(r1-r2)^2)2. 侧面积 S=PI(r1+r2)l3. 全面积 T=PIr1(l+r1。