Hi there 👋

ACM赛事时使用的算法模板

二维计算几何 线 直线与射线表示 记录直线上一点和直线的方向向量 线段 记录左右端点 多边形 数组按一定顺序记录多边形的每个顶点 矩形的各边均与某坐标轴平行的话，只记录左下角和右上角的顶点 相关判断算法 点在线的哪边 做叉积根据正负判断。 判断两个线段相交 先判断斜率是否相等 若相等，判断是否三点共线 若不共线则不相交 共线则判有无重叠——用x或者y最大最小判断即可 除了上述方法，最常用的是采用快速排斥实验和跨立实验 快速排斥实验 ​ 判断两个线段的外接矩形是否有交集，若无交则不可能相交 跨立实验 ​ 若线段相交，则其中的一条线段的两个端点必然在对于另一条线段而已在位置上是处于两边的，可以直接采用叉积根据正负判断，但两条线段共线但不相交时也可以通过跨立实验，所以一般需要加上快速排斥实验 struct Point{ double x,y; Point(double x=0,double y=0):x(x),y(y){} //向量+ Point operator +(const Point &b)const { return Point(x+b.x,y+b.y); } //向量- Point operator -(const Point &b)const { return Point(x-b.x,y-b.y); } //点积 double operator *(const Point &b)const { return x*b.x + y*b.y; } //叉积 //P^Q>0,P在Q的顺时针方向；<0，P在Q的逆时针方向；=0，P，Q共线，可能同向或反向 double operator ^(const Point &b)const { return x*b....

CAD 基础概念 FACE 表示一个有界面 有一个SURFACE的指针 由LOOP在SURFACE上限定构成 表示一个存在的面 LOOP（环） 表示面的边界 由coedges（共边）构成的回路 COEDGE（共边） 包含指向性的边（EDGE）的指针 EDGE 包含两个VERTEX指针 包含COEDGE指针 包含模型几何CURVE指针 参数曲线 参数连续性 参数曲线具有直到$n$阶连续导矢，即$n$阶连续可微，称之为$C^n$或$n$阶参数连续性。 参数曲线可能是多条曲线构成，如何保证各段在连接处的连续性。 0阶参数连续性 即x，y，z在连接点处两个参数曲线的值相等 1阶参数连续性 交点处有相同的一阶导（切线） 高阶类似 拐点不符合二阶连续性 另外，参数连续与一般的普通认知中几何连续不太一样，参数连续非常严格。 如上图，在x，y坐标下看曲线是连续的，但以参数角度上计算，在连接点处并不连续。 所以参数连续太过苛刻了。 几何连续性 存在参数变换,使得参数变换后的曲线具有 $C^n$连续性,且相应的各阶导数不为$0$,则称为具有$n$阶几何连续性，简记为$G^n$ 定义看起来有点奇怪，也有另一种说法——线段在相交处参数导数成比例即可 1阶几何连续性 满足0阶的条件下，存在公共切向量即可 2阶几何连续性 满足前阶的条件下，存在公共曲率即可 参数化 参数化的本质就是找到一组恰当的参数$t$匹配不同的样本点。不同的的样本点给出不同的参数化值，才能使得曲线美观、合理 均匀参数化 累加弦长参数化（根据长度比例确定） bezier曲线 $$ p(t) = \sum^{n}_{i=0}P_iB_{i,n}(t) \quad t\in[0,1] $$ 其中$P_i$为多边形的n+1个顶点,$B_{i,n}(t)$为伯恩施坦基本多项式。 为什么？ 有什么用？为什么是这个形式？(二项式展开) $$ B_{i,n}(t) = \cfrac{n!}{i!(n-1)!}t^i(1-t)^{n-i} $$ 一次bezier曲线 $$ \begin{align} p(t) & = P_0B_{0,1}(t)+P_1B_{1,1}(t) \\ & = (1-t)P_0+tP_1 \end{align} $$ 二次bezier曲线 $$ p(t) = (1-t)^2P_0 + 2t(1-t)P_1 + t^2P_2 $$ 三次bezier曲线 Bezier曲线比较重要的性质 起点和终点的切向量可以直接两个控制点表示，如起点切向量可以由$P_0$，$P_1$表示。...

GAMES101 MAC OS配置 brew install opencv brew install Eigen VsCode安装==clangd==、==Cmake==、==CodeLLDB==插件 在外层新建CMakeLists.txt，写入 cmake_minimum_required(VERSION 3.5) set(name "pa0") project(${name}) aux_source_directory(${name} SRC_one) add_executable(${name} ${SRC_one}) include_directories("/opt/homebrew/Cellar/eigen/3.4.0_1/include") find_package(OpenCV REQUIRED ) target_link_libraries(${name} ${OpenCV_LIBS}) target_include_directories(${name} PRIVATE ${OpenCV_INCLUDE_DIRS}) find_package(Eigen3 REQUIRED) target_link_libraries(${name} ${Eigen3_LIBS}) target_include_directories(${name} PRIVATE ${EIGEN3_INCLUDE_DIRS}) 每做一个项目修改对应name名即可。可以自己指定eigen的include路径。 创建.vscode 工作区配置 在settings.json中填写 { "cmake.sourceDirectory": "/Path/to/games101", "cmake.configureEnvironment": { "CMAKE_OSX_ARCHITECTURES": "arm64" }, "clangd.fallbackFlags": ["-std=c++17"] } 配置CmakeLists.txt所在目录后，用VsCode的插件即可自动Build。 build下生成的==compile_commands.json==将提供给clangd支持语法检测。

估计模型容量 一般来说是可以通过一个模型的参数个数来估计容量 假如特征个数为$n$，则容量为$n+1$，多1是偏置值 假如多加一层隐藏层，设隐藏层有$m$个节点，输出层有$k$个节点。则容量为$(d+1)m+(m+1)k$。类似于图的边数 K折交叉验证的目的 确定超参数。可以对每个超参数都跑一次K折交叉验证，选取最优的一个超参数。（即平均差最小 可以把K折交叉验证的K个模型全拿下来，真正做预测的时候，把测速数据集放到每个模型预测一次。 权重衰退 如何处理过拟合的情况（即模型过于复杂，直接记住了训练集。如何控制模型的复杂程度，是一个问题。 有L2正则化 $$ L(\mathbf{w}, b) + \frac{\lambda}{2} \|\mathbf{w}\|^2, $$ 其中$\lambda$为非负超参数 可得梯度下降公式 $$ \begin{aligned} \mathbf{w} & \leftarrow \left(1- \eta\lambda \right) \mathbf{w} - \frac{\eta}{|\mathcal{B}|} \sum_{i \in \mathcal{B}} \mathbf{x}^{(i)} \left(\mathbf{w}^\top \mathbf{x}^{(i)} + b - y^{(i)}\right). \end{aligned} $$ 其中$\eta\lambda$取值一般乘积小于1 丢弃法（Drop Out） 可以降低模型复杂度 即对变量$x$加入噪音 更一般的 $$ \begin{split}\begin{aligned} x' = \begin{cases} 0 & \text{ 概率为 } p \\ \frac{x}{1-p} & \text{ 其他情况} \end{cases} \end{aligned}\end{split} $$ 根据此公式对每个元素$x$进行扰动，而最终总期望不变。其中$p$为超参数 一般作用在隐藏层 模型训练的稳定性 明显的，当层数过高时，链式求导的乘积将会变得非常巨大/非常小。这将导致模型非常不稳定。 如何将梯度值处在合理的范围内？...