没有合适的资源?快使用搜索试试~ 我知道了~
Seraphim模板1
需积分: 0 0 下载量 25 浏览量
2022-08-03
14:26:46
上传
评论
收藏 1.95MB PDF 举报
温馨提示
试读
173页
Seraphim模板1
资源详情
资源评论
资源推荐
1
目录
计算几何........................................................................................................................................... 4
计算几何_main......................................................................................................................... 4
多边形和圆相交的面积 ......................................................................................................... 10
半平面交 n^2 ......................................................................................................................... 12
三维几何操作合并 ................................................................................................................. 13
三维几何 ................................................................................................................................. 15
三维旋转操作 ......................................................................................................................... 19
三维凸包_随机增量 ............................................................................................................... 19
三维凸包求重心 ..................................................................................................................... 23
随机增量最小覆盖圆 ............................................................................................................. 28
圆面积模板(新) ................................................................................................................. 29
圆的面积并(可以求交) ..................................................................................................... 30
圆的面积模板(n^2logn) ......................................................................................................... 33
直线和凸包交点(返回最近和最远点) ............................................................................. 38
最小覆盖球 ............................................................................................................................. 39
图论 ................................................................................................................................................ 41
KM ........................................................................................................................................... 41
求最小上下界网络流 ............................................................................................................. 44
求最小下界网络流_反边(optional) ................................................................................. 45
无向图最小割 ......................................................................................................................... 47
Voronoi .................................................................................................................................... 47
KD-TREE ................................................................................................................................... 55
弦图的完美消除序列 ............................................................................................................. 57
一般图最大匹配_片段 ........................................................................................................... 60
最小树形图(ElogE+V^2) ......................................................................................................... 63
最小树形图(V^3) .............................................................................................................. 65
Hopcroft .................................................................................................................................. 67
割点缩块 ................................................................................................................................. 69
割边缩块 ................................................................................................................................. 71
字符串 ............................................................................................................................................ 73
字符串最小表示 ..................................................................................................................... 73
Manacher-O(n)求每个位置为中心的最长回文串 ................................................................ 73
多个串求最长连续的子串 —— 后缀数组 o(n) ................................................................. 73
扩展_KMp ............................................................................................................................... 75
最多的重复字串(optional) ............................................................................................... 76
后缀自动机 ............................................................................................................................. 80
dc3 ........................................................................................................................................... 83
杂 .................................................................................................................................................... 85
最大团搜索算法 ..................................................................................................................... 85
极大团的计数 ......................................................................................................................... 86
Farmland ................................................................................................................................. 87
2
FFT(crazyb0y) ..................................................................................................................... 89
fft——速度一般 ..................................................................................................................... 90
FFt_speed ................................................................................................................................ 91
Romberg .................................................................................................................................. 94
多项式求根(求导二分)(optional) ................................................................................. 95
强连通分量(一遍 dfs) .......................................................................................................... 97
求区间第 K 大数_不改变值的 ............................................................................................... 98
任意两点间的第 K 短路,可重复走 ................................................................................... 101
长方体表面两点最短距离 ................................................................................................... 103
字符串的最小表示(正确的 zy) ............................................................................................ 104
最长公共子序列 ................................................................................................................... 104
Splay-Tree(带 split) .......................................................................................................... 107
动态树(ftiasch) ..................................................................................................................... 110
动态树................................................................................................................................... 113
曼哈顿最小生成树 ............................................................................................................... 117
表达式的计算 ....................................................................................................................... 121
二维树状数组 ....................................................................................................................... 121
双人零和矩阵游戏 ............................................................................................................... 122
Exact Cover(crazyb0y) ........................................................................................................... 124
数独 Dancing Links ............................................................................................................... 127
线性规划 ............................................................................................................................... 132
线性规划单纯形法_武汉网络赛 5 题 ................................................................................. 134
高精度 .......................................................................................................................................... 137
高精度开根号 ....................................................................................................................... 137
高精度类 ............................................................................................................................... 139
数学 .............................................................................................................................................. 144
牛顿迭代开根号 ................................................................................................................... 144
有多少个点在多边形内 ....................................................................................................... 145
斜线下格点统计 ................................................................................................................... 145
大整数相乘取摸 ................................................................................................................... 146
素数判定 ............................................................................................................................... 146
Pollard-Rho ............................................................................................................................ 147
O(p)求 1..p-1 的逆元 ............................................................................................................ 148
广义离散对数(不需要互质) ........................................................................................... 148
n 次剩余 ............................................................................................................................... 149
求 ax 取模 n 同余 b 的所有解及中国剩余定理 ................................................................. 154
Pell 方程求解 ........................................................................................................................ 155
莫比乌斯函数以及 gcd=1 的对数 ....................................................................................... 156
二次剩余 ............................................................................................................................... 158
Tips ............................................................................................................................................. 160
差分序列 ............................................................................................................................... 160
牛顿迭代 ............................................................................................................................... 160
求某年某月某日是星期几 ................................................................................................... 160
图同构 hash .......................................................................................................................... 160
3
综合....................................................................................................................................... 161
Stl 使用 ...................................................................................................................................... 164
java_scl .................................................................................................................................. 164
cpp ......................................................................................................................................... 166
积分表 .......................................................................................................................................... 169
基本形 公式 ......................................................................................................................... 169
平方剩余求解 ....................................................................................................................... 170
树的计数 ............................................................................................................................... 171
代数....................................................................................................................................... 171
三角公式 ............................................................................................................................... 172
积分表................................................................................................................................... 172
4
计算几何
计算几何_main
#include <iostream>
#include <cstdio>
#include <vector>
#include <string>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
#define rep(i,n) for(i=0;i<(n);i++)
#define foru(i,a,b) for(i=(a);i<=(b);i++)
#define ford(i,a,b) for(i=(a);i>=(b);i--)
double eps = 1e-8;
struct line{ double a,b,c; };
int cmp(double x){
if (x>eps) return 1;
if (x<-eps) return -1;
return 0;
}
class point{
public:
double x,y;
point(){}
point(double x,double y) : x(x) , y(y) {}
void input(){scanf("%lf %lf",&x,&y);}
point operator -(point a){a.x=x-a.x;a.y=y-a.y;return a;}
point operator +(point a){a.x=x+a.x;a.y=y+a.y;return a;}
point operator /(double a){ return point(x/a,y/a);}
bool operator == (const point &b) {return !cmp(x - b.x) && !cmp(y - b.y);}
};
double area(point a, point b, point c){
return (b.x-a.x)*(c.y-a.y) - (b.y-a.y)*(c.x-a.x);
}
double dot(point a, point b,point c){
return (b-a) ^ (c-a);
}
double dis(point a){return sqrt(a.x*a.x+a.y*a.y);}
double dis(point a,point b){return dis(b-a);}
5
//================两点求线
line point_make_line(point a, point b){
line h;
h.a=b.y-a.y;
h.b=-(b.x-a.x);
h.c=-a.x*b.y + a.y*b.x;
return h;
}
//===========旋转角度p的向量
point rotate_point(point a, double p){
point h;
h.x= a.x*cos(p) - a.y*sin(p);
h.y= a.x*sin(p) + a.y*cos(p);
return h;
}
//================点P到线段st的距离 ======================
double dis_point_segment(point p,point s,point t){
if (((p-t)^(s-t))>0&& (((p-s)^(t-s))>0)) return
fabs((p-s)*(t-s))/dis(s-t);
else return min(dis(p-s),dis(p-t));
}
//========一个点关于直线作镜像
void PointProjLine(const point &p0 ,const point &p1 ,const point &p2 , point
&cp ) {
double t = dot( p1 , p2 , p0 )/ dot( p1 , p2 , p2 ) ;
cp.x=p1.x + t*(p2.x-p1.x);
cp.y=p1.y + t*(p2.y-p1.y);
}
//===!! 或者 ===
double PointToLine (const point &p0,const point &p1,const point &p2,point &cp)
{
double d=dis(p1,p2);
double s=area(p1,p2,p0)/d;
cp.x=p0.x+s*(p2.y-p1.y)/d;
cp.y=p0.y-s*(p2.x-p1.x)/d;
return s;
}
void ReflectPoint (const point &p0,const point &p1,const point &p2,point &cp)
{
point p3;
剩余172页未读,继续阅读
阿葱的葱白
- 粉丝: 26
- 资源: 313
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功
评论0