本文内容主要来源于"Computational Geometry - Algorithms and Applications"书中第8.2章和11.4章。 对偶变换 在二维几何中，对偶性是一种将点和线之间的关系互换的概念。 在点-线对偶中，平面上的每一条直线可以映射为一个点，反之亦然。具体地，点 $(p_x,p_y)$ 的对偶是直线 $y+p_y=…

本文原始论文：链接。 符号定义 $\lfloor x\rfloor$ 表示小于等于 $x$ 的最大整数；$\{x\}=x-\lfloor x\rfloor$，即 $x$ 的小数部分；$\%$ 表示取模。 线段上的格点数 如果你熟悉exgcd和线性同余方程，那么可以直接跳过本节。 定义1 设 $x_1,y_1,x_2,y_2$ 为有理数，定义 $L(…

目录 三维几何1. 点和向量 三维几何2. 平面 三维几何3. 直线 一些废话 三维几何系列文章将会尽可能全面地介绍三维计算几何的基础知识，并简单地引入部分重要的计算机图形学内容，希望能够顺利更新完。由于这些文章本质上是我的学习笔记，没有审稿人，如有错误请务必指出！ 引用 Geometry in competitive programming, V…

本文假设需要排序的数组是 $A[]$，并且是不降序的排列 $(A[j]\ge A[i])_{j\gt i}$。 默认数组下标从 $0$ 开始。 插入排序 基础插入排序 一句话概括：从左往右遍历数组，将每次遍历到的元素 $A[i]$ 向左移动到可能的最左侧的位置 $j$，要求满足 $A[j+1]\gt A[j]$ 。（有点不严谨，但不影响理解） vo…

平面图形面积 直角坐标系 直角坐标系下计算平面图形面积是最基础的定积分应用（因为这就是定积分的几何意义）。 计算由两条抛物线：$y^2=x,y=x^2$ 所围成的图形的面积。 先确定两抛物线的角点，联立方程组： $$\begin{cases}y^2=x\\y=x^2\end{cases}\Rightarrow (0,0);(1,1)$$ 于是围成的…

常用导数表 $$\begin{aligned}(x^a)^\prime &= ax^{a-1} \\(\sin x)^\prime &= \cos x\\(\cos x)^\prime &= -\sin x\\(\tan x)^\prime &= \sec^2 x\\(a^x)^\prime &= a^x \…

定义 有 $n$ 个布尔变量 $x_0,x_1,\ldots, x_{n-1}$ 满足以下形式的逻辑表达式：$(x_i \cup x_j)\cap\cdots (x_u\cup x_{v})\cap \cdots = \text{true}$ 。要求你判断这些逻辑表达式是否能够同时成立，并给出一组构造方案的问题我们称为2-SAT问题（2-satis…