各种公式及模板

1、4.3素数.68 /284.3素数.68 #/28 /28各种公式及模板1、几何.251.1注意.251.2几何公式.251.3多边形.271.4多边形切割.301.5浮点函数.311.6面积.361.7球面.371.8三角形.381.9三维几何.401.10凸包.471.11网格.491.12圆.491.13整数函数.512、组合.54组合公式.54排列组合生成.54生成gray码.56置换(polya)56字典序全排列.57字典序组合.573、结构.58并查集.58堆.59线段树.60子段和.65子阵和.654、数论.66阶乘最后非0位.66模线性方程组.677.6有向图最小点基（邻接阵）

2、82 #/287.6有向图最小点基（邻接阵）82 /28欧拉函数.695、数值计算.705.1定积分计算（Romberg）70多项式求根（牛顿法）72周期性方程（追赶法）736、图论一NP搜索.74最大团.74最大团（n64）（faster）757、图论一连通性.777.1无向图关键点（dfs邻接阵）777.2无向图关键边（dfs邻接阵）787.3无向图的块（bfs邻接阵）797.4无向图连通分支（dfs/bfs邻接阵）807.5有向图强连通分支（dfs/bfs邻接阵）8110.1欧拉回路（邻接阵）92 /2810.1欧拉回路（邻接阵）92 #/288、图论匹配.838.1二分图最大匹配（hu

3、ngary邻接表）838.2二分图最大匹配（hungary邻接阵）848.3二分图最大匹配（hungary正向表）848.4二分图最佳匹配（kuhn_munkras邻接阵）85一般图匹配（邻接表）86一般图匹配（邻接阵）87一般图匹配（正向表）879、图论网络流.88最大流（邻接阵）88上下界最大流（邻接阵）89上下界最小流（邻接阵）90最大流无流量（邻接阵）91最小费用最大流（邻接阵）9110、图论应用.9213.3布尔母函数.120 /28 /28树的前序表转化.93树的优化算法.94拓扑排序（邻接阵）95最佳边割集.96最佳点割集.97最小边割集.98最小点割集.99最小路径覆盖.101

4、11、图论支撑树.10111.1最小生成树（kruskal邻接表）10111.2最小生成树（kruskal正向表）103最小生成树（prim+binary_heap邻接表）104最小生成树（prim+binary_heap正向表）105最小生成树（prim+mapped_heap邻接表）106最小生成树（prim+mapped_heap正向表）10811.7最小生成树（prim邻接阵）10911.8最小树形图（邻接阵）10912、图论最短路径.111最短路径（单源bellman_ford邻接阵）111最短路径（单源dijkstra+bfs邻接表）111最短路径（单源dijkstra+bfs正向

5、表）112最短路径（单源dijkstra+binary_heap邻接表）113最短路径（单源dijkstra+binary_heap正向表）114最短路径（单源dijkstra+mapped_heap邻接表）115最短路径（单源dijkstra+mapped_heap正向表）116最短路径（单源dijkstra邻接阵）117最短路径（多源floyd_warshall邻接阵）11813、应用.118Joseph问题.118N皇后构造解.119第k元素.120幻方构造.12113.6模式匹配(kmp)122逆序对数.123字符串最小表示.123最长公共单调子序列.124最长子序列.125最大子串匹

6、配.126最大子段和.127最大子阵和.12714、其它.128大数(只能处理正数)128分数.134矩阵.136线性方程组.138 /28 /28线性相关.140日期.1401、几何注意注意舍入方式（0.5的舍入方向）;防止输出-0几何题注意多测试不对称数据.整数几何注意xmult和dmult是否会出界;符点几何注意eps的使用.避免使用斜率;注意除数是否会为0.公式一定要化简后再代入.判断同一个2*PI域内两角度差应该是abs(a1-a2)pi+pi-beta;相等应该是abs(a1-a2)pi+pi-eps;需要的话尽量使用atan2，注意:atan2(0,0)=0,atan2(1,0)

7、=pi/2,atan2(-1,0)=-pi/2,atan2(0,1)=0,atan2(0,-1)=pi.crossproduct=|u|*|v|*sin(a)dotproduct=|u|*|v|*cos(a)(Pl-P0)x(P2-P0)结果的意义：正：P0,P1在P0,P2顺时针(0,pi)内负：P0,P1在P0,P2逆时针(0,pi)内0:P0,P1,P0,P2共线,夹角为0或pi误差限缺省使用1e-8!几何公式三角形:半周长P=(a+b+c)/2面积S=aHa/2=absin(C)/2=sqrt(P(P-a)(P-b)(P-c)中线Ma二sqrt(2(b八2+c八2)-a八2)/2二sq

8、rt(b八2+c八2+2bccos(A)/2角平分线Ta二sqrt(bc(b+c厂2-a八2)/(b+c)=2bccos(A/2)/(b+c)高线Ha二bsin(C)二csin(B)二sqrt(b八2-(aJ+b八2-c八2)/(2a)厂2)内切圆半径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)外接圆半径R=abc/(4S)=a/(2sin(A)=b/(2sin(B)=c/(2sin(C)四边形:D1,D2为对角线,M

9、对角线中点连线,A为对角线夹角aJ+bJ+2+dJ二D2+D2八2+4MJS=D1D2sin(A)/2(以下对圆的内接四边形)ac+bd=D1D2S=sqrt(P-a)(P-b)(P-c)(P-d),P为半周长正n边形:R为外接圆半径,r为内切圆半径中心角A=2PI/n内角C=(n-2)PI/n边长a=2sqrt(Rj-r八2)=2Rsin(A/2)=2rtan(A/2)面积S二nar/2二nr八2tan(A/2)=nR八2sin(A)/2二na八2/(4tan(A/2)圆: /28 #/283.全面积T=S+A /28弧长l=rA弦长a=2sqrt(2hr-h八2)=2rsin(A/2)弓形

10、高h=r-sqrt(rJ-a八2/4)=r(l-cos(A/2)=atan(A/4)/2扇形面积S1=rl/2=r2A/2弓形面积S2=(rl-a(r-h)/2二r八2(A-sin(A)/2棱柱:体积V二Ah,A为底面积,h为高2侧面积S=lp,l为棱长,p为直截面周长3.全面积T=S+2A棱锥:体积V二Ah/3,A为底面积,h为高(以下对正棱锥)侧面积S=lp/2,l为斜高,p为底面周长棱台:体积V=(Al+A2+sqrt(AlA2)h/3,Al.A2为上下底面积,h为高(以下为正棱台)侧面积S=(pl+p2)l/2,pl.p2为上下底面周长,l为斜高全面积T=S+A1+A2圆柱:侧面积S=

11、2PIrh全面积T=2PIr(h+r)体积V二PIrYh圆锥:母线l=sqrt(h八2+r八2)侧面积S=PIrl（卩码）id二丄逖連专wIdS=S逖連训!呂遐g/gidw逖刺wSIdW逖連专J:疽w/q（卩w+卩+iJ）id二人逖刺予（卩+1）卩1卄（1丄+1）1可。丄逖連专TT（2+1）Id=S逖連训w（卩-w）+q）wbs=需超-I:呂團/%丿id二人逖刺予G+T）Id=I逖連专Tintis_convex_v2(intn,point*p) /28 /28体积V二PIh(3(r2+r2八2)+hJ)/6球扇形:全面积T=PIr(2h+r0),h为球冠高,r0为球冠底面半径体积V=2PIrJ

12、h/31.3多边形#include#include#defineMAXN1000#defineoffset10000#defineeps1e-8#definezero(x)(x)0?(x):-(x)eps?1:(x)-eps?2:0)structpointdoublex,y;structlinepointa,b;doublexmult(pointp1,pointp2,pointp0)return(p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y);/判定凸多边形,顶点按顺时针或逆时针给出,允许相邻边共线intis_convex(intn,point*p

13、)inti,s3=1,1,1;for(i=0;in&s1|s2;i+)s_sign(xmult(p(i+1)%n,p(i+2)%n,pi)=0;returns1|s2;/判定凸多边形,顶点按顺时针或逆时针给出,不允许相邻边共线inti,s3=1,1,1;for(i=0;in&s0&s1|s2;i+)s_sign(xmult(p(i+1)%n,p(i+2)%n,pi)=0;returns0&s1|s2;/判点在凸多边形内或多边形边上,顶点按顺时针或逆时针给出intinside_convex(pointq,intn,point*p)inti,s3=1,1,1;for(i=0;in&s1|s2;i+

14、)s_sign(xmult(p(i+1)%n,q,pi)=0;returns1|s2;/判点在凸多边形内,顶点按顺时针或逆时针给出,在多边形边上返回0 /28 /28intinside_convex_v2(pointq,intn,point*p)inti,s3=1,1,1;for(i=0;in&s0&s1|s2;i+)s_sign(xmult(p(i+1)%n,q,pi)=0;returns0&s1|s2;/判点在任意多边形内,顶点按顺时针或逆时针给出/on_edge表示点在多边形边上时的返回值,offset为多边形坐标上限intinside_polygon(pointq,intn,point

15、*p,inton_edge=1)pointq2;inti=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)&(pi.x-q.x)*(p(i+1)%n.x-q.x)eps&(pi.y-q.y)*(p(i+1)%n.y-q.y)eps)returnon_edge;elseif(zero(xmult(q,q2,pi)break;elseif(xmult(q,pi,q2)*xmult(q,p(i+1)%n,q2)-eps&xmult(pi,q,p

16、(i+1)%n)*xmult(pi,q2,p(i+1)%n)-eps)count+;returncount&1;inlineintopposite_side(pointp1,pointp2,pointl1,pointl2)returnxmult(l1,p1,l2)*xmult(l1,p2,l2)-eps;inlineintdot_online_in(pointp,pointl1,pointl2)returnzero(xmult(p,l1,l2)&(l1.x-p.x)*(l2.x-p.x)eps&(l1.y-p.y)*(l2.y-p.y)eps;/判线段在任意多边形内,顶点按顺时针或逆时针给出,

17、与边界相交返回1intinside_polygon(pointl1,pointl2,intn,point*p)pointtMAXN,tt;inti,j,k=0;if(!inside_polygon(l1,n,p)|!inside_polygon(l2,n,p)return0;for(i=0;in;i+)if(opposite_side(l1,l2,pi,p(i+1)%n)&opposite_side(pi,p(i+1)%n,l1,l2)return0;elseif(dot_online_in(l1,pi,p(i+1)%n)tk+=l1;elseif(dot_online_in(l2,pi,p(

18、i+1)%n)tk+=l2;elseif(dot_online_in(pi,l1,l2)tk+=pi;for(i=0;ik;i+)for(j=i+1;jk;j+)tt.x=(ti.x+tj.x)/2;tt.y=(ti.y+tj.y)/2;if(!inside_polygon(tt,n,p)return0;return1;pointintersection(lineu,linev)pointret=u.a;doublet=(u.a.x-v.a.x)*(v.a.y-v.b.y)-(u.a.y-v.a.y)*(v.a.x-v.b.x)/(u.a.x-u.b.x)*(v.a.y-v.b.y)-(u.a

19、.y-u.b.y)*(v.a.x-v.b.x);ret.x+=(u.b.x-u.a.x)*t;ret.y+=(u.b.y-u.a.y)*t;returnret;pointbarycenter(pointa,pointb,pointc)lineu,v;u.a.x=(a.x+b.x)/2;u.a.y=(a.y+b.y)/2;u.b=c;v.a.x=(a.x+c.x)/2;v.a.y=(a.y+c.y)/2;v.b=b;returnintersection(u,v);/多边形重心pointbarycenter(intn,point*p)pointret,t;doublet1=0,t2;inti;re

20、t.x=ret.y=0;for(i=1;ieps)t=barycenter(p0,pi,pi+1);ret.x+=t.x*t2;ret.y+=t.y*t2;t1+=t2;if(fabs(t1)eps)ret.x/=t1,ret.y/=t1;returnret;1.4多边形切割/多边形切割/可用于半平面交#defineMAXN100#defineeps1e-8#definezero(x)(x)0?(x):-(x)eps;pointintersection(pointu1,pointu2,pointv1,pointv2)pointret=u1;doublet=(u1.x-v1.x)*(v1.y-v2.y)-(u1.y-v1.y)*(v1.x-v2.x)/(u1.x-u2.x)*(v1.y-v2.y)-(u1.y-u2.y)*(v1.x-v2.x);ret.x+=(u2.x-u1.x)*t;ret.y+=(u2.y-u1.y)*t;r