Mxiaocao Blog

二维计算几何通常处理平面上的点、向量、线段、多边形、圆等图形。而其核心在于熟练使用向量和叉积 最常用的点/向量结构可以这样理解 123456789101112131415struct point{ double x,y;};point operator+(point a,point b){ return {a.x + b.x,a.y+b.y};}point operator-(point a,point b){ return {a.x-b.x,a.y-b.y};}point operator*(point a,double k){ return {a.x*k,a.y*k};} 点表示位置，向量表示方向和长度，在代码里他们通常用一个结构体存 最重要的两个运算是点积和叉积 点积： 123double dot(point a,point b){ return a.x*b.x + a.y*b.y;} 点积主要用来判断夹角、投影、距离 若dot(a,b) > 0，夹角小于90°；若等于0，两个向量垂直；若小于0，夹角大于90° 叉积： 123double...

在二维计算几何中，凸包是最经典的算法之一。无论是求解最远点对、判断点集区域还是进行动态规划的几何优化，凸包都是不可或缺的知识点 一、定义凸多边形：是指所有内角大小都在 [0,𝜋] 范围内的简单多边形 凸包：在平面上能包含所有给定点的最小凸多边形叫做凸包，严谨地说，对于给定平面上的点集 ，所有包含 的凸集的交集 ，被称为 的凸包 但说白了可以理解为用一个橡皮筋包含住所有给定点的形态，凸包用最小的周长围住了给定的所有点。例如一堆点中，内部点不会出现在凸包上，只有最外层的点会构成凸包 凸包常见用途包括： 求最外层边界 求最远点对，配合旋转卡壳 判断点是否在点集形成的区域内 凸多边形面积、周长 半平面交、动态规划优化中的几何结构 二、Andrew 算法求凸包求凸包常用地有Andrew算法和Graham扫描法。由于Andrew算法好写、稳定、常数小，复杂度是O(n log n)，所以介绍Andrew算法 Andrew算法地核心思想是维护一个单调栈，分两步求出下凸壳和上凸壳： 双关键字排序： 先按x坐标从小到大排序，若x相同则按y坐标排序。排序后，最左下角的点和最右上角的点必定在...

适用条件：单源、包含负边权、判断是否存在负环。 [注]：在没有负边权的正权图里，优先使用 Dijkstra，因为 SPFA 容易被特殊构造的数据卡成 的龟速。 Bellman-Ford 算法是单源最短路径算法，求一个起点 到其他所有点的最短路径。一个有 个点的图，给每个点 次机会查询邻居，是否有到起点 的更短的路径，如果有就更新；经过 轮查询和更新，就得到了所有点到起点 的最短路径。 有个现实的模型，即”问路”。每个十字路口站着一个警察；在某个路口，路人问一个警察：”怎么到 最近？”如果这个警察不知道，他就会问相邻几个路口的警察。这些警察可能也不知道，他们会继续问新的邻居。这样传递下去，最后肯定有个警察是 路口的警察，他会把 的信息返回给他的邻居，邻居再返回给邻居。最后所有的警察都知道怎么走到 ，而且是最短的路。从 返回信息到所有其他点的过程，就像在一个平静的池塘中，从 丢下一个石头，荡起的涟漪一圈圈向外扩散，这一圈圈涟漪经过的路径，肯定是最短的。 在这个模型中，能体现 Bellman-Ford 算法思想的是：警察不需要知道到 的完整路径，只需要知道从自...

最小生成树是一个无向连通图中的一颗包含图中所有顶点的树（即无环），且具有最小总权重 而图的两个基本元素是点和边，与此对应，有两种算法可以构造MST，这两种算法都基于贪心法: Kruskal（加边）：排序+DSU，适合稀疏图（） Prim（加点）：优先队列，适合稠密图（） Kruskal对图中所有边进行贪心。从最短的边开始，把它加入T中；在剩下的边中找最短的边，加入T中；继续这个过程，直到T中包含n-1条边，或者所有点都在T中。 必备概念记下三种核心结构： struct Edge：用于存储每一条边的起点、终点和权重，并重载 < 运算符 fa[x]：DSU的父节点数组，用于计入点x属于哪个连通块 find[x]：DSU的寻根函数，并带有路径压缩功能 下面让我们代入一个场景： 你是一名极其抠门的包工头，要把 个深山里的村庄连通起来，你手里有一本账本，上面记录了所有可以修的路以及它们的报价 你的策略极其简单粗暴：便宜的先修，能省则省。 沙盘推演：A、B、C 三个村庄，AB 要 1 万，BC 要 2 万，AC 要 10 万 我们跟着思路走一遍这个三角圈： 第一步： 账本排序 你把账...

女王生日快乐！ 愿你的每一天都如今天般闪耀，愿你被世界温柔以待。 祝你岁岁常欢愉，年年皆胜意。 2026.05.24

5.2.8 Tarjan算法Tarjan算法可用于求解强连通分量以及无向图中的割点和割边（又称桥） 一、连通性概念那么什么叫强连通分量呢，什么叫割点呢，什么又是割边呢？所以接下来我要从两个方面讲解一下相关的概念 无向图的连通性无向图中所有能互通（你能到达我，我能到达你）的点组成了一个”连通分量(Connected Component)”。而在一个连通分量中有一些关键的点，如果删掉它们，会把这个连通分量断为两个甚至更多，这种称为 割点(Cut Vertex)。与之类似的，在一个连通分量中如果删除一条边，把这个连通分量分成了两个，这条边成为 割边（Cut Vertex，又称为 桥(bridge)） 而研究割点和割边，我们还能继续拓展出 双连通(Block / 2-Connected Component) 问题，即如何实现一个没有割点和割边的图： 在一个连通图中任选两点，如果他们之间至少存在两条”点不重复”的路径，称为点双连通，一个图中的点双连通极大子图称为 点双连通分量。点双连通分量去掉任意一个点，其他点仍然是连通的，即点双连通分量中没有割点。 类似地，如果任意两点之间至少存在两条”...

Educational Codeforces Round 190 (Rated for Div. 2)A. Optimal Purchase（implementation）（math） Ques门钥匙 题意 You have a group of students who need access to an online course. Two types of access keys are available in the store: Individual key: costs dollars and gives access to one student. Group key: costs dollars and gives access to a group of up to three students inclusive. A group key can also be used for fewer students (one or two), and its price does not change. Your task is to determine...

3. Codeforces Round 996 (Div. 2)A. Two Frogs（800）（constructive algorithms）（games）（greedy）（math） Ques门钥匙 题意 Roaming through the alligator-infested Everglades, Florida Man encounters a most peculiar showdown. There are lilypads arranged in a row, numbered from to from left to right. Alice and Bob are frogs initially positioned on distinct lilypads, and , respectively. They take turns jumping, starting with Alice. During a frog’s turn, it can jump either one space to the left or...

Lambda表达式Lambda 表达式是现代编程语言中一个非常重要的特性，特别是在 Java 8及更高版本、C#、Python、JavaScript 和 c++ 等语言中被广泛使用。 Lambda 表达式还是很常见且重要的，我看机房的一些学长写题解的时候会使用到。下面以 c++ 为例展开讨论。 1. 什么是 Lambda 表达式简单来说，Lambda 表达式是一个匿名函数。它没有函数名，但可以有参数列表、函数主体和返回值。它的核心思想是将行为（一段代码）作为数据进行传递。 简单来说，Lambda 表达式就是写在函数内部的小函数。 2. 为什么需要 Lambda 表达式 代码简洁 可读性强 于 c++ 而言 ，Lambda 表达式是在 C++11 标准中引入的，并在 C++14、C++17、C++20 中得到了增强。它是 C++ 迈向现代、高效编程风格的重要标志。 3. c++ Lambda 的基础语法1[捕获列表](参数列表) -> 返回类型 { 函数体 } [捕获列表]：核心且必须,是用于定义如何在 Lambda 内部访问外部作用域的变量。 ...

2. Codeforces Round 997 (Div. 2)A. Shape Perimeter（800）（constructive algorithms）（math） Ques门钥匙 题意 There is an by square stamp on an infinite piece of paper. Initially, the bottom-left corner of the square stamp is aligned with the bottom-left corner of the paper. You are given two integer sequences and , each of length . For each step from to , the following happens: Move the stamp units to the right and units upwards. Press the stamp onto the paper, leaving an by colored square at ...