《几何公式浙大》由会员分享，可在线阅读，更多相关《几何公式浙大（121页珍藏版）》请在金锄头文库上搜索。
1、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 阶乘最后非
2、0位464.2 模线性方程组474.3 素数484.4 欧拉函数495、数值计算 505.1 定积分计算(Romberg)505.2 多项式求根(牛顿法)525.3 周期性方程(追赶法)536、图论NP搜索 546.1 最大团546.2 最大团(n64)(faster)557、图论连通性 577.1 无向图关键点(dfs邻接阵)577.2 无向图关键边(dfs邻接阵)587.3 无向图的块(bfs邻接阵)597.4 无向图连通分支(dfs/bfs邻接阵)607.5 有向图强连通分支(dfs/bfs邻接阵)617.6 有向图最小点基(邻接阵)628、图论匹配 638.1 二分图最大匹配(hung
3、ary邻接表)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
4、.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、图论最短路径 91
5、12.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邻接阵)98
6、13、应用 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的舍入
7、方向);防止输出-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(
8、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(b2+c2)-a2)/2=sqrt(b2+c2+2bccos(A)/24. 角平分线 Ta=sqrt(bc(b+c)2-a2)/(b+c)=2bccos(A/2)/(b+c)5. 高
9、线 Ha=bsin(C)=csin(B)=sqrt(b2-(a2+b2-c2)/(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. a2+b2+c2+d2=D12+D22+4M22. S=D1D2sin(A)/2(以下对圆的内
10、接四边形)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(R2-r2)=2Rsin(A/2)=2rtan(A/2)4. 面积 S=nar/2=nr2tan(A/2)=nR2sin(A)/2=na2/(4tan(A/2)圆:1. 弧长 l=rA2. 弦长 a=2sqrt(2hr-h2)=2rsin(A/2)3. 弓形高 h=r-sqrt(r2-a2/4)=r(1-cos(A/2)=atan(A/4)/24. 扇形面积 S
11、1=rl/2=r2A/25. 弓形面积 S2=(rl-a(r-h)/2=r2(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=PIr2h圆锥:1. 母线 l=sqrt(h2+r2)2. 侧面积 S=PIrl3. 全面积 T=PIr(l+r)4. 体积 V=PIr2h/3圆台:1. 母线 l=sqrt(h2+(r1-r2)2)2. 侧面积 S=PI(r1+r2)l3. 全面积 T=PIr1(l+r1
