Khasehemwy-CSDN博客

原创 3D软渲染器记录

行矢量,列矢量和矩阵当使用列矢量时，矩阵对矢量进行的变换按从右往左的顺序阅读。使用行矢量时，顺序就变成从左往右了。（想象对结果进行转置，再把表达式代入这个转置，就能从列矢量得到行矢量了）....................................

2021-03-24 20:31:52 795 1

问题描述：给n个点，给出圆的r，求在给定r下，圆最多能覆盖多少点？O(n3)：显然肯定有2个点在最多覆盖圆的边界上。可以枚举每2个点，求出以该两点连线为弦的圆，再枚举每个点是否在圆内。O(n2logn)：类似扫描线的做法，以每一个点为圆心化圆，枚举与其相交得圆，保存交点和角度，按角度排序后，扫一遍。参考：[POJ 1981] Circle and Points(单位圆覆盖最多的点）例题：POJ 1981 Circle and Points//O(n2logn)int GetCircleMo

2021-11-19 20:47:05 948

原创以经纬度求球上两点距离：经纬度板子

例题：POJ 2354 Titanic#include<bits/stdc++.h>#define ll long long#define IOS std::ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);#define DEBUG cout<<",here\n";#define Rep(i,l,r) for(int i=(l);i<=(r);i++)using namespace std;const dou

2021-11-18 16:07:35 211

原创求最大完全子图(最大团)（匈牙利算法）

最大完全子图：在图中找一个最大的子集，该子集中的任意两个点都相互连通。相关概念：独立集：任意两点都不相连的顶点的集合独立数：独立集中顶点的个数完全子图：任意两点都相连的顶点的集合最大完全数：最大完全子图中顶点的个数最大完全数=原图的补图的最大独立数最大独立数=顶点数-最大匹配数这样，就可以求出最大完全数。先建立原图的补图，再求出补图的最大匹配数（用匈牙利算法），用总顶点数减去补图最大匹配数，即可得出最大完全数。（最大完全图具体有哪些顶点也可得出。把补图最大匹配的点去除，得出补图的最大独立

2021-11-12 16:17:07 2406

原创求散点最近点对（分治）

散点最近点对：给一堆二维点，求两个点距离的最小值。求解：把点按x排序，取x值的中值x=xmid，以x=xmid为中线分割点，分别求左边和右边的最小距离，最后再找有没有两个点分属于左右子集，距离小于左子集和右子集的最小距离。当前集的最小距离为这3个值中的一个。一直左右分治到只剩两个点。P1429 平面最近点对#include<bits/stdc++.h>#define ll long long#define IOS std::ios::sync_with_stdio(false);c

2021-10-29 17:17:06 186

原创求散点最小覆盖矩形（凸包最小外接矩形）

问题描述：给一堆散点，要求一个最小面积的矩形能覆盖所有的散点。思路：先散点建立凸包，然后用旋转卡壳的思想枚举边，枚举到每条边时，再找对应的最左、最右、最上方的一个点，这些点一定在外接矩形上，找到面积最小的矩形即可。例题：最小矩形覆盖#include<bits/stdc++.h>#define ll long long#define lf double#define IOS std::ios::sync_with_stdio(false);cin.tie(0);cout.tie(0

2021-10-23 22:23:38 1543

原创求多边形相交面积（暴力 / 半平面交）

暴力：貌似只适用于求两个多边形的相交面积，但是可以求任意多边形（凹凸）。1.设两个多边形点集为P1，P2，相交区域点集为P。2.遍历P1的点是否在P2内，若在内部，则加入点集P；对P2也做相同操作。3.遍历P1的边和P2的边，求出两个多边形的交点，将交点加入P。4.求点集P的面积。半平面交：这个只适用凸包，但是可以求任意个凸包最终相交的面积。1.把每个凸包的点按照逆时针排序。（当然也看自己的算法是要什么顺序，大多数需要逆时针）2.将每个凸包的边放入边集L。3.求边集L的半平面交，再求半平

2021-04-28 14:22:40 1156 2

原创求多边形的核（半平面交）

多边形核：多边形的核相当于在某一点能看到所有顶点（不穿过边），这些点的集合就是多边形的核。题目：POJ - 1279细节：判断点是不是顺时针输入的，可以判断多边形面积，如果面积为负，则输入顺序是顺时针，需要改成逆时针（多数算法都是以逆时针顺序为基础）#include<bits/stdc++.h>#define ll long long#define lf double#define IOS std::ios::sync_with_stdio(false);cin.tie(0);co

2021-04-28 12:57:02 167

原创求矩形面积并（扫描线算法）

定义：有若干个边平行于坐标轴的矩形，问他们覆盖的面积总和。扫描线算法：选取一个坐标轴平行于扫描线（图中是x轴），每次扫描线移动到矩形起始边，就标记相应的范围+1，移到终止边时就-1。每次移动到新边时，计算这次和上次扫描线的间距d，新加的面积就是已覆盖的长度*d。已覆盖面积可用线段树统计。例题：HDU - 1542#include<bits/stdc++.h>#define ll long long#define lf double#define IOS std::ios::s

2021-04-27 17:14:43 529

原创凸包最大内切圆（二分+半平面交）

定义：给一个凸包，求这个凸包里能放的最大圆(一般要求半径)。凸多边形的范围等价于各个边的半平面交，可以发现，当凸包各个边向内收缩r时，内切圆的半径就会减少r。当缩到半平面交恰好不存在时，收缩的r就是内切圆的最大半径了。可以二分找收缩的r值，若收缩后半平面交不为空集，则可以存在此半径的圆。题目：POJ - 3525#include<bits/stdc++.h>#define ll long long#define lf double#define IOS std::ios::syn

2021-04-26 12:18:30 694

原创凸包最小外切圆（最小覆盖圆）

定义：给出平面上的一些点，求覆盖这些点的最小圆。具体问题可见hdu 2215解决：1.求这些离散点的凸包；2.枚举凸包上任意3点形成的三角形，求这些三角形的外切圆，找出所有外切圆中半径最大的一个。细节：1.若枚举的三个点构成钝角三角形，则最大半径为最长边的一半否则，半径 r=a*b*c/(4*S) ，其中S为三角形面积，用叉积很好求。2.钝角三角形判断：若最长边为c，则a*a+b*b<c*c（类比直角三角）//n个点,每次输入一个点的x,y值,每个点有0.5大小的半径,求最小覆盖圆

2021-04-24 20:55:43 656

原创计算几何模板

1.杂项1.1pi计算pi = acos(-1);1.2减小误差尽量少用三角函数、除法、开方、求幂、取对数运算1.0 / 2.0 ∗ 3.0 / 4.0 ∗ 5.0 = ( 1.0 ∗ 3.0 ∗ 5.0 ) / ( 2.0 ∗ 4.0 )a/b > c ---- a > bc1.3判等(x-y)<eps//取代 (x==y)1.4负零小心不要输出-0，比如：double a = -0.00001;printf("%.4lf",a);1.5反三角

2021-04-22 11:55:25 420

原创最近公共祖先(LCA)（倍增算法）

时间复杂度：预处理O(nlogn)，每次查询O(logn)。例题：P3379 【模板】最近公共祖先（LCA）#include<bits/stdc++.h>#define ll long long#define lf double#define IOS std::ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);#define DEBUG cout<<",here\n";#define Rep(i,l,r) for(i

2021-02-18 14:52:19 164

原创二维差分数组：O(1)时间进行区间修改

二维差分数组：每次修改区域为O(1)O(1)O(1)，每次查询为O(nm)O(nm)O(nm)。例题：P3397 地毯#include<bits/stdc++.h>#define ll long long#define lf double#define IOS std::ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);#define DEBUG cout<<",here\n";#define Rep(i,l,r)

2021-02-17 20:24:07 237

原创左偏树(可合并堆)（包括pbds库）

左偏树(可合并堆)：有时需要将两个堆合并，此时每次都对一个pop()再在另一个push() ，太慢了。此时直接合并堆会更快，设堆1有size1个节点，堆2有size2个节点，则合并堆1堆2的复杂度为：O(log(size1))+O(log(size2))O(log(size1))+O(log (size2))O(log(size1))+O(log(size2))。例题：P3377 【模板】左偏树（可并堆）手写左偏树版：#include<bits/stdc++.h>#define l

2021-02-17 16:43:24 410

原创最优比率环(最优比率问题)

最优比率环：给定有点权和边权的图，要求找一个环，使环的点权和与边权和的比值最大。解决方法：和01分数规划类似，但新权值的式子有所不同。来源：https://blog.csdn.net/hzoi_ztx/article/details/54898323此时求最大比率的式子与01规划的式子有所不同（总算式加个负号）。核心：取定一个 r 值以后，带入最短路的新的dis[]更新公式，再判断是否存在至少一个负环(找出一个负环即可)，存在负环和不存在负环两种情况指示了 r 应如何取下一个值，直到到达指定精度

2021-02-13 12:17:52 405

原创最优比率生成树(最优比率问题)

前置知识：01分数规划最优比率生成树：带权无向图G，对于每条边 ei ，都有 value 和 cost ，要求一棵生成树T，最大(小)化 ∑valuei/costi\sum{value_i/cost_i}∑valuei/costi。套用01分数规划模型，每次定下 r 的值后，重新计算边权为weighti=valuei−r∗costiweight_i=value_i-r*cost_iweighti=valuei−r∗costi ，再在此基础跑最小生成树算法选取边。每次二分出 r 后都重新赋值边

2021-02-11 17:00:45 559

原创 01分数规划问题(最优比率问题)：选取“权值/花费”总和最大的方案

01分数规划问题：每件物品有valuevaluevalue和costcostcost，要求选取kkk个物品，使∑\sum_ {}∑(valueivalue_{i}valuei / costicost_{i}costi) 最大。求解：原理在这(讲得很详细)。设答案为rrr，令 weight[i]=value[i]−r∗cost[i]weight[i]=value[i]-r*cost[i]weight[i]=value[i]−r∗cost[i] ，每次确定一个rrr值，把rrr当作已知常量，求出每个

2021-02-11 10:46:12 239

原创 K度限制最小生成树

K度限制最小生成树含义：在最小生成树的基础上，限制了某一点v0的度最大为K (<=K) ，要求满足此条件的最小生成树。求解方法：先在删去点v0的基础上跑最小生成树。此时有可能生成M个最小生成树(连通块)，那么v0的度就至少为M，因为v0必须与每个连通块相连才能最终生成一棵树。然后每棵树选择一个和v0相连权值最小的边，连接此边，生成M度最小生成树。求出每个点到v0的最短路径上的权值最大的边dp[i]。遍历与v0相连但不在树中的边edge[v0][v]，假设连接其中一条边，则应删去该边对应的

2021-02-10 14:41:20 514

原创 vs下MySQL报错“Incorrect string value”解决方法

网上什么设置MySQL字符集之类的都试了，还是会插入中文报错。命令行插入中文没错，所以就考虑是vs某些设置与MySQL的设置冲突了。因为vs默认编码是GB2312，所以添加下方命令即可：set names ‘gbk’...

2021-02-09 12:01:26 160

原创 windows下vs配置c++使用mysql库

mysql8.0只能找到x64版本的，但是windows写c++程序默认是x86版本，配置起来就很麻烦。步骤：创建工程后，选择x64解决方案。一定要新的工程先换成x64。去项目属性页添加：附加包含目录，附加库目录，附加依赖项，对应相应的MySQL路径，基础操作。去配置属性 -> 调试 -> 环境，设置path为MySQL的bin文件夹。将MySQL的lib文件夹的libmysql.dll(不是.lib)文件复制到C:\Windows\System32下。完成...

2021-02-05 20:06:20 181 1

原创网络流：有上下界的最大流

有上下界的意思：每条管道的流量必须在范围 [L,R] 内，即在普通最大流问题上增加了下界限制。主要分为无源点汇点和有源点汇点两类问题。1.无源汇点有上下界的最大流此类问题一般为：给n个点，及m根pipe，每根pipe用来流躺液体的，单向的，每时每刻每根pipe流进来的物质要等于流出去的物质，要使得m条pipe组成一个循环体，里面流躺物质。并且满足每根pipe一定的流量限制，范围为[Li,Ri].即要满足每时刻流进来的不能超过Ri(最大流问题)，同时最小不能低于Li。解决：普通的最大流可以视作下界为

2021-02-02 20:31:17 456

原创 MySQL记录

记录：MySQL使用Begin…End语句的一个坑：写一个触发器，执行单条语句是OK的。想执行多条语句，尝试在代码中加入BEGIN END。但一加BEGIN END就报错，错误信息也很诡异，只说某一行出错了，不符合Mysql的语句规范，提示信息就个’’。查了文档，并没有发现BEGIN END有什么特别要注意的地方。反复查找，参考了这里：http://bbs.csdn.net/topics/390542425 13楼的回复。说是没有定义查询界定符导致，导致编译器将;识别为全部语句的结束，导致

2021-02-02 10:47:05 83

原创树状数组：单点修改区间查询

树状数组：每个节点储存所有子节点和该节点对应的值之和，每个节点的值的求解有一个lowbit()函数的关系。复杂度：更新单点信息O(logn)，求区间和O(logn).参考：树状数组详解 , 树状数组详解2核心函数：ll A[600005],n;//A数组存的是所有子节点加上自身的和,不同实现可以有不同含义ll lowbit(ll X){return X&(-X);}void update(ll I,ll K){ //在i位置加上k while(I <= n

2021-01-31 17:06:47 145

原创状态压缩，二进制储存状态

二进制储存状态：假设有1e9个灯，要记录其开或关的状态。用数组肯定爆空间了，此时可以用1e8个二进制位为10位的数来储存状态，每个二进制位为1或0表示开或关。二进制运算： C/C++中直接表示二进制（其他进制）：在C/C++ 中天然的支持除10进制之外的三种进制的表示, 其前缀分别为:二进制 : 0b八进制 : 0十六进制 : 0x1.二进制例: int x = 0b1001; // x = 92.八进制例：int y = 074; // x = 6

2021-01-29 20:12:03 420

原创刷题记录

当需要使用ll时，常数也记得强制转化为llll tmp=(ll)1<<i;例如：D. Ehab the Xorcist

2020-11-05 20:27:03 81

转载最长上升/非降子序列，长度查找及输出序列(典型例题记录)

复杂度均为 O(nlogn)长度查找： int n; scanf("%d",&n); for (int i=1;i<=n;i++) scanf("%d",&a[i]); if (n==0) //0个元素特判一下 { printf("0\n"); return 0; } d[1]=a[1]; //初始化 int len=1; for (int i=2;i<=n;i++)

2020-10-08 12:09:06 193

原创差分数组：O(1)时间进行区间修改，查询仍为O(n)

差分数组定义：原数组 a : 5,8,4,3,15差分数组 b : 5,3,−4,−1,12差分数组就是原数组对应项和它前面那项的差值。原数组中的第i项就等于：∑j=1j=ib[j]{\mathop{ \sum }\limits_{{j=1}}^{{j=i}}{{b \left[ j \right] }}}j=1∑j=ib[j]差分前缀和：原数组：a: 5,8,4,3,15它的差分数组：b: 5,3,−4,−1,12它的差分前缀和（就是差分数组的前缀和）：c: 5,8,4,3,15可以

2020-10-02 16:01:28 244

原创 Codeforces Round #672 (Div. 2) B. Rock and Lever

题意：对于任意的 a[i],a[j] (i!=j)，求 a[i]&a[j]>=a[i]^a[j] 的数量。t组数据，每组n个a[i]。显然1&1(=1)>1^1(=0)，所以只要两个数的二进制位数相同，就满足。反之一定不满足。那只需要比较每两个数的二进制位数即可。例如在 [ pow(2,4),pow(2,5) )区间内的数一定位数相同，所以按从小到大排序a[i]，当a[i]与a[i-1]满足时，说明其位数相同，记录mk++，当下一个数仍然满足时就相当于 a[i],a[i-

2020-09-25 11:26:19 140

原创 Min25算法：求N极大时的素数个数 || 素数和

模板记录：因为N极大（1e10以上），所有很可能爆long long，所以加了一个__int128模板#include<bits/stdc++.h>#define ll __int128using namespace std;typedef long long LL;const int N = 1000010;void scan(__int128 &x)//输入{ x = 0; int f = 1; char ch; if((ch =

2020-09-24 10:58:01 278

原创 Int128模板

void scan(__int128 &x)//输入{ x = 0; int f = 1; char ch; if((ch = getchar()) == '-') f = -f; else x = x*10 + ch-'0'; while((ch = getchar()) >= '0' && ch <= '9') x = x*10 + ch-'0'; x *= f;}void _print(_

2020-09-21 11:41:36 196

原创主席树：求区间第k小值 || 求区间小于等于k的元素数量

模板记录：离散化复杂度为O(nlogn)，构建基础主席树复杂度为O(nlogn)，统计并插入的复杂度是O(nlogn+nlogn)=O(nlogn)，询问的复杂度是O(mlogn)。#include<bits/stdc++.h>#define MAXN 200010const int INF=0x3f3f3f3f;using namespace std;int n,m,a[MAXN],b[MAXN],l,r,k;int root[MAXN];struct Tree{

2020-09-16 18:14:14 358 1

原创最小环问题（Floyd算法）

最小环问题：在有向/无向图中，求构成的所有环中的权值和最小值。当模板就行了，也不太难。例题：寻找最小环（无向图，把每条边存两次就行了，分别以u/v为起点）#include<bits/stdc++.h>#define MAXN 105#define INF 1000000000#define ll long longusing namespace std;ll n,m,ans=INF;ll u,v,d;ll dis[MAXN][MAXN],mp[MAXN][MAXN];

2020-07-29 14:38:59 609

原创最小树形图（朱刘算法）

最小树形图：类似最小生成树。给定有向图，求用给定边所能构成的最小树。朱刘算法：贪心算法。可以想到每次都找每个点的入边中最小的一个来构成树，如果构成了，就是最小的。但是构成过程中可能会出现环，这时候就需要缩点。而且因为每个点只选取一条入边，所以构成的环一定是简单环，没有必要用tarjan求强连通分量来找缩点。这样编写难度会小很多。每次找到环以后需要更新权值，规则是这样的：对于每条指向环的边，该边边权减去所指向点的最小入边。更新后继续找环，直到没有环，即找到最小树形图。例题：最小树形图 #incl

2020-07-28 22:05:44 418

原创次小生成树（最小生成树算法+倍增LCA）

次小生成树：显然就是除开最小生成树外最小的一个生成树。非严格次小生成树：权值和 <= 最小生成树。严格次小生成树：权值和 < 最小生成树求解：每次在非最小生成树的边里找一条，将这条边加入树，此时一定形成环，再删去环中除该边外最大的一条边。依次枚举每条边，找到加入边-删除边最小的一种情况，即可求出非严格次小生成树。当加入边的权值=删去边的权值时，就不是严格的了，所以可以再记录环中第二大的边，当非严格时，删去第二大的边，即可变为严格的。寻找环中的最大/次大边：先求出边的两端点

2020-07-26 21:46:27 549

原创 Trie字典树(前缀树)

很久以前就写过了，稍微记录下字典树：提供多个单词，每次查找一个单词，这时可以用字典树。查询1次的复杂度为O(m)，m为单词长度。实现：举个例子，要记录trie单词。起初添加一个虚根节点。每个节点有字母表数的子节点(如全是小写就有26个子节点)，初始为0，表示没有这个子节点。记录trie，那么虚根节点的son[ ‘t’-‘a’ ]=1，end=0，表示没有到达单词结尾。然后t节点的son[ ‘r’-‘a’ ]=1 …以此类推，到e时记录end=1。查询时就一次看有没有子节点以及最后end是否为1，若

2020-07-25 16:19:44 137

空空如也

空空如也