各种公式及模板Word下载.docx
- 文档编号:6210596
- 上传时间:2023-05-06
- 格式:DOCX
- 页数:17
- 大小:19.26KB
各种公式及模板Word下载.docx
《各种公式及模板Word下载.docx》由会员分享,可在线阅读,更多相关《各种公式及模板Word下载.docx(17页珍藏版)》请在冰点文库上搜索。
6.1最大团...74
6.2最大团(n<
64)(faster)75
7、图论—连通性...77
7.1无向图关键点(dfs邻接阵)77
7.2无向图关键边(dfs邻接阵)78
7.3无向图的块(bfs邻接阵)79
7.4无向图连通分支(dfs/bfs邻接阵)80
7.5有向图强连通分支(dfs/bfs邻接阵)81
7.6有向图最小点基(邻接阵)82
8、图论—匹配...83
8.1二分图最大匹配(hungary邻接表)83
8.2二分图最大匹配(hungary邻接阵)84
8.3二分图最大匹配(hungary正向表)84
8.4二分图最佳匹配(kuhn_munkras邻接阵)85
8.5一般图匹配(邻接表)86
8.6一般图匹配(邻接阵)87
8.7一般图匹配(正向表)87
9、图论—网络流...88
9.1最大流(邻接阵)88
9.2上下界最大流(邻接阵)89
9.3上下界最小流(邻接阵)90
9.4最大流无流量(邻接阵)91
9.5最小费用最大流(邻接阵)91
10、图论—应用...92
10.1欧拉回路(邻接阵)92
10.2树的前序表转化...93
10.3树的优化算法...94
10.4拓扑排序(邻接阵)95
10.5最佳边割集...96
10.6最佳点割集...97
10.7最小边割集...98
10.8最小点割集...99
10.9最小路径覆盖...101
11、图论—支撑树...101
11.1最小生成树(kruskal邻接表)101
11.2最小生成树(kruskal正向表)103
11.3最小生成树(prim+binary_heap邻接表)104
11.4最小生成树(prim+binary_heap正向表)105
11.5最小生成树(prim+mapped_heap邻接表)106
11.6最小生成树(prim+mapped_heap正向表)108
11.7最小生成树(prim邻接阵)109
11.8最小树形图(邻接阵)109
12、图论—最短路径...111
12.1最短路径(单源bellman_ford邻接阵)111
12.2最短路径(单源dijkstra+bfs邻接表)111
12.3最短路径(单源dijkstra+bfs正向表)112
12.4最短路径(单源dijkstra+binary_heap邻接表)113
12.5最短路径(单源dijkstra+binary_heap正向表)114
12.6最短路径(单源dijkstra+mapped_heap邻接表)115
12.7最短路径(单源dijkstra+mapped_heap正向表)116
12.8最短路径(单源dijkstra邻接阵)117
12.9最短路径(多源floyd_warshall邻接阵)118
13、应用...118
13.1Joseph问题...118
13.2N皇后构造解...119
13.3布尔母函数...120
13.4第k元素...120
13.5幻方构造...121
13.6模式匹配(kmp)122
13.7逆序对数...123
13.8字符串最小表示...123
13.9最长公共单调子序列...124
13.10最长子序列...125
13.11最大子串匹配...126
13.12最大子段和...127
13.13最大子阵和...127
14、其它...128
14.1大数(只能处理正数)128
14.2分数...134
14.3矩阵...136
14.4线性方程组...138
14.5线性相关...140
14.6日期...140
1、几何
1.1注意
1.注意舍入方式(0.5的舍入方向);
防止输出-0.
2.几何题注意多测试不对称数据.
3.整数几何注意xmult和dmult是否会出界;
符点几何注意eps的使用.
4.避免使用斜率;
注意除数是否会为0.
5.公式一定要化简后再代入.
6.判断同一个2*PI域内两角度差应该是
abs(a1-a2)<
beta||abs(a1-a2)>
pi+pi-beta;
相等应该是
eps||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.crossproduct=|u|*|v|*sin(a)
dotproduct=|u|*|v|*cos(a)
9.(P1-P0)x(P2-P0)结果的意义:
正:
<
P0,P1>
在<
P0,P2>
顺时针(0,pi)内
负:
逆时针(0,pi)内
0:
<
共线,夹角为0或pi
10.误差限缺省使用1e-8!
1.2几何公式
三角形:
1.半周长P=(a+b+c)/2
2.面积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))/2
4.角平分线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^2
2.S=D1D2sin(A)/2
(以下对圆的内接四边形)
3.ac+bd=D1D2
4.S=sqrt((P-a)(P-b)(P-c)(P-d)),P为半周长
正n边形:
R为外接圆半径,r为内切圆半径
1.中心角A=2PI/n
2.内角C=(n-2)PI/n
3.边长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=rA
2.弦长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)/2
4.扇形面积S1=rl/2=r^2A/2
5.弓形面积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=2PIrh
2.全面积T=2PIr(h+r)
3.体积V=PIr^2h
圆锥:
1.母线l=sqrt(h^2+r^2)
2.侧面积S=PIrl
3.全面积T=PIr(l+r)
4.体积V=PIr^2h/3
圆台:
1.母线l=sqrt(h^2+(r1-r2)^2)
2.侧面积S=PI(r1+r2)l
3.全面积T=PIr1(l+r1)+PIr2(l+r2)
4.体积V=PI(r1^2+r2^2+r1r2)h/3
球:
1.全面积T=4PIr^2
2.体积V=4PIr^3/3
球台:
2.全面积T=PI(2rh+r1^2+r2^2)
3.体积V=PIh(3(r1^2+r2^2)+h^2)/6
球扇形:
1.全面积T=PIr(2h+r0),h为球冠高,r0为球冠底面半径
2.体积V=2PIr^2h/3
1.3多边形
#include<
stdlib.h>
math.h>
#defineMAXN1000
#defineoffset10000
#defineeps1e-8
#definezero(x)(((x)>
0?
(x):
-(x))<
eps)
#define_sign(x)((x)>
eps?
1:
((x)<
-eps?
2:
0))
structpoint{doublex,y;
};
structline{pointa,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){
inti,s[3]={1,1,1};
for(i=0;
i<
n&
&
s[1]|s[2];
i++)
s[_sign(xmult(p[(i+1)%n],p[(i+2)%n],p[i]))]=0;
returns[1]|s[2];
//判定凸多边形,顶点按顺时针或逆时针给出,不允许相邻边共线
intis_convex_v2(intn,point*p){
s[0]&
returns[0]&
//判点在凸多边形内或多边形边上,顶点按顺时针或逆时针给出
intinside_convex(pointq,intn,point*p){
s[_sign(xmult(p[(i+1)%n],q,p[i]))]=0;
//判点在凸多边形内,顶点按顺时针或逆时针给出,在多边形边上返回0
intinside_convex_v2(pointq,intn,point*p){
//判点在任意多边形内,顶点按顺时针或逆时针给出
//on_edge表示点在多边形边上时的返回值,offset为多边形坐标上限
intinside_polygon(pointq,intn,point*p,inton_edge=1){
pointq2;
inti=0,count;
while(i<
n)
for(count=i=0,q2.x=rand()+offset,q2.y=rand()+offset;
n;
if(zero(xmult(q,p[i],p[(i+1)%n]))&
(p[i].x-q.x)*(p[(i+1)%n].x-q.x)<
eps&
(p[i].y-q.y)*(p[(i+1)%n].y-q.y)<
returnon_edge;
elseif(zero(xmult(q,q2,p[i])))
break;
elseif(xmult(q,p[i],q2)*xmult(q,p[(i+1)%n],q2)<
-eps&
xmult(p[i],q,p[(i+1)%n])*xmult(p[i],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)<
(l1.y-p.y)*(l2.y-p.y)<
eps;
//判线段在任意多边形内,顶点按顺时针或逆时针给出,与边界相交返回1
intinside_polygon(pointl1,pointl2,intn,point*p){
pointt[MAXN],tt;
inti,j,k=0;
if(!
inside_polygon(l1,n,p)||!
inside_polygon(l2,n,p))
return0;
if(opposite_side(l1,l2,p[i],p[(i+1)%n])&
opposite_side(p[i],p[(i+1)%n],l1,l2))
elseif(dot_online_in(l1,p[i],p[(i+1)%n]))
t[k++]=l1;
elseif(dot_online_in(l2,p[i],p[(i+1)%n]))
t[k++]=l2;
elseif(dot_online_in(p[i],l1,l2))
t[k++]=p[i];
k;
for(j=i+1;
j<
j++){
tt.x=(t[i].x+t[j].x)/2;
tt.y=(t[i].y+t[j].y)/2;
inside_polygon(tt,n,p))
}
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.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;
ret.x=ret.y=0;
for(i=1;
n-1;
if(fabs(t2=xmult(p[0],p[i],p[i+1]))>
eps){
t=barycenter(p[0],p[i],p[i+1]);
ret.x+=t.x*t2;
ret.y+=t.y*t2;
t1+=t2;
if(fabs(t1)>
ret.x/=t1,ret.y/=t1;
1.4多边形切割
//多边形切割
//可用于半平面交
#defineMAXN100
intsame_side(pointp1,pointp2,pointl1,pointl2){
returnxmult(l1,p1,l2)*xmult(l1,p2,l2)>
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;
//将多边形沿l1,l2确定的直线切割在side侧切割,保证l1,l2,side不共线
voidpolygon_cut(int&
n,point*p,pointl1,pointl2,pointside){
pointpp[100];
intm=0,i;
i++){
if(same_side(p[i],side,l1,l2))
pp[m++]=p[i];
same_side(p[i],p[(i+1)%n],l1,l2)&
!
(zero(xmult(p[i],l1,l2))&
zero(xmult(p[(i+1)%n],l1,l2))))
pp[m++]=intersection(p[i],p[(i+1)%n],l1,l2);
for(n=i=0;
m;
i||!
zero(pp[i].x-pp[i-1].x)||!
zero(pp[i].y-pp[i-1].y))
p[n++]=pp[i];
if(zero(p[n-1].x-p[0].x)&
zero(p[n-1].y-p[0].y))
n--;
if(n<
3)
n=0;
1.5浮点函数
//浮点几何函数库
//计算crossproduct(P1-P0)x(P2-P0)
doublexmult(doublex1,doubley1,doubl
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 各种 公式 模板