各種公式及模板

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樹的優(yōu)化算法.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