Dreadnought Code Library for World Finals 2016

Final List

Tier 1

• 多边形与圆面积交
• 二维几何
• 半平面交
• 三维几何操作合并
• 三维凸包
• 圆面积模板
• 三角形的心
• 凸包上快速询问
• 经纬度求球面对短距离
• 最大团
• Hungarian
• 带花树
• Hopcroft
• 素数判定/整数分解
• 日期公式
• 线性规划
• FFT
• Manacher/Z ALgo
• 后缀数组（倍增）
• 后缀自动机
• 字符串最小表示
• Splay Tree
• LCT
• 直线下个点个数
• JavaIO
• vimrc

Tier 2

• Delaunay 三角剖分

• 后缀树（With Pop Front）

• Dominator Tree

• Scherier-Sims

• DLX

• 最小树形图（求方案）

• 最小覆盖球

• 环状LCS

• 费用流

• 轻重链剖分

• 二次剩余

• Pell方程

• 无向图最小割

• 长方体表面两点最短距离

墓地

• KD Tree
• 极大团
• 动态最小生成树
• Romberg
• NTT
• FWT
• DC3
• 图同构Hash
• 消圈

结论

• 弦图相关
• 各种公式，结论
• 积分表

List of Todo

To be checked

• 二维几何
• 三角形的心
• Hopcroft
• 经纬度

New/Improve

• Hungarian Algorithm (With proper initialization and n != m)
• Suffix Tree (With walker/With erase)
• FFT（实数精度改进版/虚部Trick）
• 主流
• 德劳内三角剖分
• 循环赛构造
• 斯坦纳三元系构造
• 解双人博弈纳什均衡
• 三角形内外垂心
• 最大团
• 最大独立集
• 极大团计数
• SAT Solver
• k上升子序列
• 凸包上快速询问
• 动态树
• 有限域分解多项式
• 扩展KMP/Manacher

Merge

• 二维几何基础
• 半平面交（Lolicon Version）
• 圆的面积模板
• 圆和多边形面积交
• 圆的交点和切线（需修正+重圆警告）
• 三维几何基础
• 三维凸包
• 三维凸包重心
• JAVA读入优化
• .vimrc

List of Contents

Algorithms and Data Structures

• Dominator Tree

• Fast Walsh Transform (With And/Or variation)

• Hungarian Algorithm (With proper initialization)

• Suffix Tree (With walker/With erase)

• Edmond Algorithm

• Schreier-Sims Algorithm

• 二维几何基础

• 点在多边形内

• 半平面交（Lolicon Version）

• 三角形内外心

• 圆的面积模板

• 圆和多边形面积交

• 圆的交点和切线（需修正+重圆警告）

• 三维几何基础

• 三维凸包

• 三维凸包重心

• 质因数分解

• 离散对数

• 二次剩余

• Pell方程

• FFT（实数精度改进版/虚部Trick/整数版）

• 主流

• 全局最小割

• 最大匹配Hopcroft

• 一般图最大匹配

• 弦图完美消除序列

• 扩展KMP/Manacher

• 后缀树组DC3

• 后缀自动机

• 环装同构/最小表示

• 环状最长公共子串

• 动态树

• 十字链表DLX

• 最大团

• 最大独立集

• 极大团计数

• 单纯形

• Simpson/Romberg

• 直线下格点个数

• 直线和凸包交点

• 最小覆盖球

• 长方体表面最短距离

• 动态最小生成树

• Splay

• 德劳内三角剖分

• 循环赛构造

• 公共x元组构造

• 解双人博弈纳什均衡

• SAT Solver

• k上升子序列

• 有限域分解多项式

Math Facts

• Primes for DFT

• Bernoulli Number/Formula

• 日期公式

• 常用数学公式、定理及结论

• 代数、图论与组合、几何、三角、数论、积分表

Other

• JAVA读入优化

• .vimrc