I
Zhejiang University
ICPC Team
Routine Library
by WishingBone (Dec. 2002)
Last Update (Nov. 2004) by Riveria
II
1、 几何...........................................................................................................................1
1.1 注意...................................................................................................................1
1.2 几何公式...........................................................................................................1
1.3 多边形...............................................................................................................3
1.4 多边形切割.......................................................................................................6
1.5 浮点函数...........................................................................................................7
1.6 面积.................................................................................................................12
1.7 球面.................................................................................................................13
1.8 三角形.............................................................................................................14
1.9 三维几何.........................................................................................................16
1.10 凸包.................................................................................................................23
1.11 网格.................................................................................................................25
1.12 圆.....................................................................................................................25
1.13 整数函数.........................................................................................................27
2、 组合.................................................................................................................30
2.1 组合公式..................................................................................................................30
2.2 排列组合生成..........................................................................................................30
2.3 生成 gray 码.............................................................................................................32
2.4 置换(polya)..............................................................................................................32
2.5 字典序全排列..........................................................................................................33
2.6 字典序组合..............................................................................................................33
3、............... 结构 34
3.1 并查集......................................................................................................................34
3.2 堆..............................................................................................................................35
3.3 线段树......................................................................................................................36
3.4 子段和......................................................................................................................41
3.5 子阵和......................................................................................................................41
4、..数论 42
4.1 阶乘最后非 0 位......................................................................................................42
4.2 模线性方程组..........................................................................................................43
4.3 素数..........................................................................................................................44
4.4 欧拉函数..................................................................................................................45
III
5、 数值计算.................................................................................................................46
5.1 定积分计算(Romberg) ............................................................................................46
5.2 多项式求根(牛顿法)...............................................................................................48
5.3 周期性方程(追赶法)...............................................................................................49
6、......... 图论—NP 搜索 50
6.1 最大团......................................................................................................................50
6.2 最大团(n<64)(faster) ...............................................................................................51
7、 图论—连通性 53
7.1 无向图关键点(dfs 邻接阵) .....................................................................................53
7.2 无向图关键边(dfs 邻接阵) .....................................................................................54
7.3 无向图的块(bfs 邻接阵) .........................................................................................55
7.4 无向图连通分支(dfs/bfs 邻接阵) ...........................................................................56
7.5 有向图强连通分支(dfs/bfs 邻接阵) .......................................................................57
7.6 有向图最小点基(邻接阵).......................................................................................58
8、....... 图论—匹配 59
8.1 二分图最大匹配(hungary 邻接表).........................................................................59
8.2 二分图最大匹配(hungary 邻接阵).........................................................................60
8.3 二分图最大匹配(hungary 正向表).........................................................................60
8.4 二分图最佳匹配(kuhn_munkras 邻接阵) ...............................................................61
8.5 一般图匹配(邻接表)...............................................................................................62
8.6 一般图匹配(邻接阵)...............................................................................................63
8.7 一般图匹配(正向表)...............................................................................................63
9、....... 图论—网络流 64
9.1 最大流(邻接阵).......................................................................................................64
9.2 上下界最大流(邻接阵)...........................................................................................65
9.3 上下界最小流(邻接阵)...........................................................................................66
9.4 最大流无流量(邻接阵)...........................................................................................67
9.5 最小费用最大流(邻接阵).......................................................................................67
10、....... 图论—应用 68
10.1 欧拉回路(邻接阵).................................................................................................68
10.2 树的前序表转化....................................................................................................69
10.3 树的优化算法........................................................................................................70
10.4 拓扑排序(邻接阵).................................................................................................71
10.5 最佳边割集............................................................................................................72
10.6 最佳点割集............................................................................................................73
10.7 最小边割集............................................................................................................74
10.8 最小点割集............................................................................................................75
10.9 最小路径覆盖........................................................................................................77
11、......... 图论—支撑树 77
11.1 最小生成树(kruskal 邻接表).................................................................................77
11.2 最小生成树(kruskal 正向表).................................................................................79
11.3 最小生成树(prim+binary_heap 邻接表)...............................................................80
11.4 最小生成树(prim+binary_heap 正向表)...............................................................81
11.5 最小生成树(prim+mapped_heap 邻接表) ............................................................82
IV
11.6 最小生成树(prim+mapped_heap 正向表) ............................................................84
11.7 最小生成树(prim 邻接阵).....................................................................................85
11.8 最小树形图(邻接阵) .............................................................................................85
12、......... 图论—最短路径 87
12.1 最短路径(单源 bellman_ford 邻接阵)..................................................................87
12.2 最短路径(单源 dijkstra+bfs 邻接表)....................................................................87
12.3 最短路径(单源 dijkstra+bfs 正向表)....................................................................88
12.4 最短路径(单源 dijkstra+binary_heap 邻接表) .....................................................89
12.5 最短路径(单源 dijkstra+binary_heap 正向表) .....................................................90
12.6 最短路径(单源 dijkstra+mapped_heap 邻接表)...................................................91
12.7 最短路径(单源 dijkstra+mapped_heap 正向表)...................................................92
12.8 最短路径(单源 dijkstra 邻接阵)...........................................................................93
12.9 最短路径(多源 floyd_warshall 邻接阵) ...............................................................94
13、......... 应用 94
13.1 Joseph 问题.............................................................................................................94
13.2 N 皇后构造解.........................................................................................................95
13.3 布尔母函数............................................................................................................96
13.4 第 k 元素................................................................................................................96
13.5 幻方构造................................................................................................................97
13.6 模式匹配(kmp)......................................................................................................98
13.7 逆序对数................................................................................................................99
13.8 字符串最小表示....................................................................................................99
13.9 最长公共单调子序列..........................................................................................100
13.10 最长子序列........................................................................................................101
13.11 最大子串匹配....................................................................................................102
13.12 最大子段和........................................................................................................103
13.13 最大子阵和........................................................................................................103
14、 .............. 其它 104
14.1 大数(只能处理正数)...........................................................................................104
14.2 分数......................................................................................................................110
14.3 矩阵......................................................................................................................112
14.4 线性方程组..........................................................................................................114
14.5 线性相关..............................................................................................................116
14.6 日期......................................................................................................................116
1
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;
相等应该是
abs(a1-a2)<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. cross product = |u|*|v|*sin(a)
dot product = |u|*|v|*cos(a)
9. (P1-P0)x(P2-P0)结果的意义:
正: <P0,P1>在<P0,P2>顺时针(0,pi)内
负: <P0,P1>在<P0,P2>逆时针(0,pi)内
0 : <P0,P1>,<P0,P2>共线,夹角为 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)
