「已注销」-CSDN博客

转载洋葱三角剖分

给定一个平面上的点集，目标是构造一个点集的三角剖分。从Lennes 1911年二次时间复杂度的源算法到Chazelle 1991线性时间复杂度的算法，前人已经做了许多关于提高三角剖分算法效率的研究。这里的焦点是关于一种特殊的三角剖分，一种基于对点集进行“剥洋葱皮”操作。考虑平面上一个有 n 个点的集合 S 。计算 S 的凸包，并且设 S' 为在凸包内的点集。然

2013-09-24 17:35:29 1835

转载螺旋三角剖分

点集的螺旋三角剖分是基于集合螺旋凸包的三角剖分图。凸螺旋线可以通过如下方法构造：从一个特定的端点开始（比如给定方向上的最小点），这里取有最小 x 坐标的点。通过那个点构造一条铅垂线。按照一个给定的方向旋转线（总保持顺时针或者是逆时针方向），直到线“击” 出另一个顶点。将两个点用一条线段连接。重复步骤3和步骤4，但是总忽略已经击出的点。大体上，这个过程类似于计算凸包的卷包裹

2013-09-24 17:34:27 1465

转载凸多边形最小周长外接矩形

这个问题和最小面积外接矩形相似。我们的目标是找到一个最小盒子（就周长而言）外接多边形 P 。有趣的是通常情况下最小面积的和最小周长的外接矩形是重合的。有人不禁想问这是不是总成立的。下面的例子回答了这个问题：多边形（灰色的）及其最小面积外接矩形（左边的）和最小周长外接矩形（右边的）。现在，给定一个方向，我们可以算出 P 的端点，以此来确定一

2013-09-24 17:34:26 2717

转载凸多边形最小面积外接矩形

给定一个凸多边形 P ，面积最小的能装下 P （就外围而言）的矩形是怎样的呢？从技术上说，给定一个方向，能计算出 P 的端点并且构由此造出外接矩形。但是我们需要测试每个情形来获得每个矩形来计算最小面积吗？谢天谢地，我们不必那么干。对于多边形 P 的一个外接矩形存在一条边与原多边形的边共线。上述结论有力地限制了矩形的可能范围。我们不仅不必去检测所有可能的方向，而

2013-09-24 17:33:25 9825

转载凸多边形间最大距离

给定两个凸多边形 P 和 Q，目标是需要找到点对 (p,q) （p 属于 P 且 q 属于 Q）使得他们之间的距离最大。很直观地，这些点不可能属于他们各自多边形的内部。这个条件事实上与直径问题非常相似：两凸多边形 P 和 Q 间最大距离由多边形间的对踵点对确定。虽然说法一样，但是这个定义与给定凸多边形的对踵点对的不同。与凸多边形间的对踵点对本质上的区别在于切

2013-09-24 17:33:05 2334

转载凸多边形间最小距离

给定两个非连接（比如不相交）的凸多边形 P 和 Q，目标是找到拥有最小距离的点对 (p,q) （p 属于 P 且 q 属于Q）。事实上，多边形非连接十分重要，因为我们所说的多边形包含其内部。如果多边形相交，那么最小距离就变得没有意义了。然而，这个问题的另一个版本，凸多边形顶点对间最小距离对于相交和非相交的情况都有解存在。回到我们的主问题：直观的，确定最小

2013-09-24 17:31:59 4338

转载旋转卡壳——凸多边形的宽度

凸多边形的宽度定义为平行切线间的最小距离。这个定义从宽度这个词中已经略有体现。虽然凸多边形的切线有不同的方向，并且每个方向上的宽度（通常）是不同的。但幸运的是，不是每个方向上都必须被检测。我们假设存在一个线段 [a,b]，以及两条通过 a 和 b 的平行线。通过绕着这两个点旋转这两条线，使他们之间的距离递增或递减。特别的，总存在一个特定旋转方向使得

2013-09-24 17:31:13 1514

转载旋转卡壳——凸多边形直径

凸多边形直径我们将一个多边形上任意两点间的距离的最大值定义为多边形的直径。确定这个直径的点对数可能多于一对。事实上，对于拥有 n 个顶点的多边形，就可能有 n 对“直径点对”存在。一个多边形直径的简单例子如左图所示。直径点对在图中显示为被平行线穿过的黑点（红色的一对平行线）. 直径用浅蓝色高亮显示。显然，确定一个凸多边形 P 直径的点对不可能在多边

2013-09-24 17:29:46 1907

转载并查集

http://www.cnblogs.com/ACShiryu/archive/2011/09/17/union.html并查集的程序设计：为了解释并查集的原理，我将举一个更有趣的例子。话说江湖上散落着各式各样的大侠，有上千个之多。他们没有什么正当职业，整天背着剑在外面走来走去，碰到和自己不是一路人的，就免不了要打一架。但大侠们有一个优点就是讲义气

2013-08-17 19:16:53 1005

转载图解数据结构（10）——排序

http://www.cppblog.com/guogangj/archive/2009/11/13/100876.html十四、排序（Sort）这可能是最有趣的一节。排序的考题，在各大公司的笔试里最喜欢出了，但我看多数考得都很简单，通常懂得冒泡排序就差不多了，确实，我在刚学数据机构时候，觉得冒泡排序真的很“精妙”，我怎么就想不出呢？呵呵，其实冒泡通常是效率最差的排序算法，差多少？请看

2013-08-13 22:53:48 900

转载图解数据结构（7）——二叉查找树及平衡二叉查找树

http://www.cppblog.com/guogangj/archive/2009/10/26/99502.html这篇将是最有难度和挑战性的一篇，做好心理准备！十、二叉查找树（BST）前一篇介绍了树，却未介绍树有什么用。但就算我不说，你也能想得到，看我们Windows的目录结构，其实就是树形的，一个典型的分类应用。当然除了分类，树还有别的作用，我们可以利用树建立

2013-08-13 22:51:51 934

转载图解数据结构（9）——左偏树

转载自http://www.cppblog.com/guogangj/archive/2009/10/30/99833.html树这个数据结构内容真的很多，上一节所讲的二叉堆，其实就是一颗二叉树，这次讲的左偏树（又叫“左翼堆”），也是树。二叉堆是个很不错的数据结构，因为它非常便于理解，而且仅仅用了一个数组，不会造成额外空间的浪费，但它有个缺点，那就是很难合并两个二叉堆，对于“合并”

2013-08-13 22:48:17 799

转载图解数据结构（8）——二叉堆

转载自http://www.cppblog.com/guogangj/archive/2009/10/29/99729.html首先说说数据结构概念——堆（Heap），其实也没什么大不了，简单地说就是一种有序队列而已，普通的队列是先入先出，而二叉堆是：最小先出。这不是很简单么？如果这个队列是用数组实现的话那用打擂台的方式从头到尾找一遍，把最小的拿出来不就行了？行啊，可是出队的操作是

2013-08-13 22:43:34 892

转载图解数据结构（6）——树及树的遍历

转载自http://www.cppblog.com/guogangj/archive/2009/10/16/98772.html树，顾名思义，长得像一棵树，不过通常我们画成一棵倒过来的树，根在上，叶在下。不说那么多了，图一看就懂：当然了，引入了树之后，就不得不引入树的一些概念，这些概念我照样尽量用图，谁会记那么多文字？树这种结构还可以表示成下面这种方式，可见

2013-08-13 22:41:52 1035

转载图解数据结构（5）——散列法及哈希表

转载自http://www.cppblog.com/guogangj/archive/2009/10/15/98699.html数组的特点是：寻址容易，插入和删除困难；而链表的特点是：寻址困难，插入和删除容易。那么我们能不能综合两者的特性，做出一种寻址容易，插入删除也容易的数据结构？答案是肯定的，这就是我们要提起的哈希表，哈希表有多种不同的实现方法，我接下来解释的是最常用的一种方法

2013-08-13 22:33:21 1875

转载图解数据结构（4）——二分法查找法

转载自http://www.cppblog.com/guogangj/archive/2009/10/15/98649.html如何从数组里找一个元素的位置？如果排列是无序的，我们只能从头到尾找，但如果排列是有序的，我们则可以用别的更好的方法，二分查找法就类似我们在英汉词典里找一个单词的方法。如下图所示（假如我们要查找的数字是“88”）：下面我给出了一段demo代码，来

2013-08-13 22:21:03 968

转载图解数据结构（3）——队

转载自http://www.cppblog.com/guogangj/archive/2009/10/14/98588.html前一篇讲了栈（Stack），队和栈其实只有一个差别，栈是先进后出，队是先进先出，如图：从图中可以看出，队有两个常用的方法，Enqueue和Dequeue，顾名思义，就是进队和出队了。队和栈一样，既可以用数组实现，也可以用链表实现

2013-08-13 22:17:09 821

转载图解数据结构（2）——栈

转载自http://www.cppblog.com/guogangj/archive/2009/10/14/98565.html前一篇讲解了最基本的东西，这篇就稍微前进一点点，讲一下栈，栈在英文中叫Stack，翻译成中文又叫“堆栈”，但决不能称为“堆”，这个要搞清楚，我们说的“栈”和“堆栈”指的都是Stack这种数据结构，但“堆”却是另外一个概念了，这里且不提。栈最大特点是先进后出

2013-08-13 22:00:09 1012

转载图解数据结构（1）——大圈表示法、动态数组和单向链表

转载自http://www.cppblog.com/guogangj/archive/2009/10/13/98476.html《数据结构》这门课是计算机专业的核心课程，但往往却让人头痛，因为比较抽象，当然了，也许你足够聪明，并不觉得它有多难，但对我而言，是有点难度，后来我仔细想了想，到底哪里难？我得出这么个结论：长篇大论，缺乏图表。现在的人都喜欢看电影，看电视剧，很少人还热衷于看小说吧，

2013-08-13 21:48:06 1004

原创栈练习3

http://wikioi.com/problem/3139/// File Name: 3137.cpp// Author: bo_jwolf// Created Time: 2013年08月13日星期二 15时21分34秒#include#include#include#include#include#include#include#include#include

2013-08-13 16:32:37 858

原创 C++的输出精度控制

使用这些格式需要声明包含long flags( ) const 返回当前的格式标志。long flays(long newflag) 设置格式标志为newflag，返回旧的格式标志。long setf(long bits) 设置指定的格式标志位，返回旧的格式标志。long setf(long bits,long field)将field指定的格式标志位置为bits，返回旧的格式

2013-07-18 11:26:00 1981 4

原创中国剩余定理

中国剩余定理介绍在《孙子算经》中有这样一个问题：“今有物不知其数，三三数之剩二（除以3余2），五五数之剩三（除以5余3），七七数之剩二（除以7余2），问物几何？”这个问题称为“孙子问题”，该问题的一般解法国际上称为“中国剩余定理”。具体解法分三步：找出三个数：从3和5的公倍数中找出被7除余1的最小数15，从3和7的公倍数中找出被5除余1 的最小数21，最后从5和7的公倍数

2013-07-17 15:07:03 3124 2

原创灌水问题

倒水问题的经典形式是这样的：　　“假设有一个池塘，里面有无穷多的水。现有2个空水壶，容积分别为5升和6升。问题是如何只用这2个水壶从池塘里取得3升的水。”　　当然题外是有一些合理的限制的，比如从池塘里灌水的时候，不管壶里是不是已经有水了，壶一定要灌满，不能和另一个壶里的水位比照一下“毛估估”（我们可以假设壶是不透明的，而且形状也不同）；同样的，如果要把水从壶里倒进池塘里，一定要都倒

2013-07-17 10:57:50 1709

原创【专辑】图论复习

http://blog.csdn.net/tclh123/article/details/6407352updating ... 05.09...08.08...10.28... 存图方法。零、连通性无向图割点、桥有向图强连通SCC一、最短路Dijkstra +heapB

2013-05-29 21:07:04 890

原创分治法最近点对问题

在二维平面上的n个点中，如何快速的找出最近的一对点，就是最近点对问题。一种简单的想法是暴力枚举每两个点，记录最小距离，显然，时间复杂度为O(n^2)。在这里介绍一种时间复杂度为O(nlognlogn)的算法。其实，这里用到了分治的思想。将所给平面上n个点的集合S分成两个子集S1和S2，每个子集中约有n/2个点。然后在每个子集中递归地求最接近的点对。在这里，一个关键的

2013-05-29 20:53:20 4117

原创母函数详解

母函数（Generating function）详解在数学中，某个序列的母函数是一种形式幂级数，其每一项的系数可以提供关于这个序列的信息。使用母函数解决问题的方法称为母函数方法。母函数可分为很多种，包括普通母函数、指数母函数、L级数、贝尔级数和狄利克雷级数。对每个序列都可以写出以上每个类型的一个母函数。构造母函数的目的一般是为了解决某个特定的问题，因此选用何种母函数视乎序列本身

2013-05-28 22:19:51 2260

原创母函数

定义 [编辑]母函数就是一列用来展示一串数字的挂衣架— 赫伯特·维尔夫, [1]普通母函数 [编辑]普通母函数就是最常见的母函数。一般来说，序列的母函数是：如果是某个离散随机变量的概率质量函数，那么它的母函数被称为一个概率母函数。多重下标的序列也可以有母函数。例如，序列的母函数是。指数母函数 [编辑]

2013-05-22 13:47:26 1227

原创二分图——最大匹配数（最小覆盖数）、最大独立数、最小路径覆盖、带权最优匹配

文本内容框架：§1图论点、边集和二分图的相关概念和性质§2二分图最大匹配求解匈牙利算法、Hopcroft-Karp算法§3二分图最小覆盖集和最大独立集的构造§4二分图最小路径覆盖求解§5二分图带权最优匹配求解Kuhn-Munkers算法§6小结每章节都详细地讲解了问题介绍，算法原理和分析，算法流程，算法实现四部分内容，力求彻底

2013-05-19 17:04:52 2853

原创图论模版

转载于http://blog.acmol.com邻接表求强连通分量Tarjan求双连通分量Tarjan最近公共祖先Tarjan最短路SPFA最短路dijkstra优先队列优化最短路Floyd最短路/负权回路判定Bellman最小生成树prim优先队列优化并查集最小生成树Kruskal二分图匹配二分图多重匹配网络流ISAP算法最小费用最大流欧拉路的判断求欧拉路圈套圈算法拓扑排序

2013-05-17 15:05:54 931

原创映射二叉堆

适妞namespace MappingBinaryHeap{/* DS: Datastructure to show the value Heap: 1.Ds:value 2.idx:index pos: The position for each index len: The v

2013-05-17 14:54:30 1635

原创 POJ 图论

POJ 2449 Remmarguts' Date(中等) AChttp://acm.pku.edu.cn/JudgeOnline/problem?id=2449题意：经典问题：K短路解法：dijkstra+A*(rec)，方法很多相关：http://acm.pku.edu.cn/JudgeOnline/showcontest?contest_id=1144

2013-05-09 22:17:42 4919 1

原创图论知识点列表

基本图算法图广度优先遍历深度优先遍历拓扑排序割边割点强连通分量Tarjan算法双连通分量强连通分支及其缩点图的割边和割点最小割模型、网络流规约2-SAT问题欧拉回路哈密顿回路最小生成树Prim算法Kruskal算法(稀疏图)Sollin算法次小生成树第k小生成树最优比例生成树最小树形图最小度限制生成树平面点的欧

2013-05-07 11:59:55 1076

原创 KMP算法

本文转至点击打开链接这是一朵奇葩，明明自己就是大牛，还老是喜欢膜拜我们这些小菜学弟（平时开玩笑时，哈哈）KMP算法假设主串：S: S[1] S[2] S[3] ……S[n]模式串：T: T[1] T[2] T[3]…..T[m]现在我们假设主串第i 个字符与模式串的第j(j主串: S[1]...S[i-j+1]...S[i-1]S[i]...

2013-04-30 20:58:28 980

原创图像有用区域

点击打开链接题目有点坑，注意先输入N，后输入M，优化在图的最外层再添加一层// File Name: nyoj92.cpp// Author: bo_jwolf// Created Time: 2013年04月30日星期二 15:20:24#include#include#include#include#include#include#include#i

2013-04-30 15:45:44 1082

原创 nyist_ACM

ACM进阶计划 ACM队不是为了一场比赛而存在的，为的是队员的整体提高。大学期间，ACM队队员必须要学好的课程有：l C/C++两种语言 l 高等数学 l 线性代数 l 数据结构 l 离散数学 l 数据库原理 l 操作系统原理 l 计算机组成原理 l 人工智能 l 编译原理 l 算法设计与分析除此之外，我希望你们能掌握一些其它

2013-04-29 22:45:17 1791 1

原创 ACM知识点分类

第一类：基础算法（1）基础算法：枚举，贪心，递归，分治，递推，构造，模拟（2）动态规划：背包问题，树形dp，状态压缩dp，单调性优化，插头dp（3）搜索：dfs，bfs，记忆化搜索，优化与剪枝，双广，A*，IDA*，跳舞链第二类：数据结构（1）简单数据结构：链表，栈和队列，串，树和二叉树，图，排序与检索（2）树形结构：线段树，树状数组，字典

2013-04-29 22:28:00 1009

原创网络流题目集锦

最大流 POJ 1273 Drainage Ditches POJ 1274 The Perfect Stall (二分图匹配) POJ 1698 Alice's Chance POJ 1459 Power Network POJ 2112 Optimal Milking (二分) POJ 2455 Secret Milking Machine (二分) POJ 318

2013-04-29 22:26:47 1005

原创 kmp总结及其应用

这个是我的学长关于KMP的总结，感觉比较好。。。上几天发现遇到一道kmp题,发现对其理解不够透彻,然后这两天对kmp重新做了一个总结.并在poj上找了部分题目作为测试.因为帖子里头贴代码,有点长,所以就只写思路了, 具体代码实现可以参考 http://www.cnblogs.com/yefeng1627kmp含义　　克努斯-莫里斯-普拉特算法，一种字符串查找

2013-04-29 20:42:24 1162

原创 ACM 训练大纲（CSUST_ACM）

ACM 训练大纲Changsha University of Science & TechnologyJuly 31, 20121 推荐题库• http://ace.delos.com/usaco/美国的OI 题库，如果是刚入门的新手，可以尝试先把它刷通，能够学到几乎全部的基础算法极其优化，全部的题解及标程还有题目翻译可以baidu 一个叫N

2013-04-29 16:56:00 2422 2

原创八数码的八境界

研究经典问题，空说不好，我们拿出一个实际的题目来演绎。八数码问题在北大在线测评系统中有一个对应的题，题目描述如下：EightTime Limit: 1000MS Memory Limit: 65536K Special JudgeDescription The 15-puzzle has been around

2013-04-28 14:44:16 1418 1

2013年蓝桥杯辅导资料

空空如也