单调队列 单调队列是主要用于解决类似滑动窗口类问题的数据结构：在长度为​的序列中，求每个长度为​的区间的区间最值问题，时间复杂度为 deque<int> q; int v[N]; int n,m; int main(){ cin >> n >> m; for (int i = 1;i <= n;++i){ cin >> v[i]; } for (int i = 1;i <= n;++i){ if (!q.empty() && i - q.front() &...

半平面交算法 对于平面上的所有有向边（角度范围​） 将向量按照角度排序(atan2(y,x)) 按顺序扫描所有向量，用双端队列维护双平面交轮廓 只要队尾的两个线和队头的两个线的交点在当前直线的右侧（因为保存左侧），将队尾或者队头删除 用直线的参数方程存储直线 时间复杂度 int cnt; struct Line{ PDD st,ed; }line[N]; int q[N]; PDD pg[N],ans[N]; int sign(double x){ if (fabs(x) < eps) return 0; if (x < 0) retu...

Andrew算法 将所有点排序，x为第一关键字，y为第二关键字 从左到右维护上半部分，从右至左维护下半部分 栈顶反向延长线的顺时针方向就留下，反之删除栈顶 double andrew(){ sort(q,q+n); int top = 0; for (int i = 0;i < n;++i){ while (top >= 2 && area(q[stk[top - 1]],q[stk[top]],q[i]) <= 0){ if (area(q[stk[top - 1]],q[stk[top]]...

树上dp整理 大体思路 以树为载体的最优值问题是建立在遍历的基础上的。不同状态的表示往往按照节点分类，状态转移往往发生在父节点和子节点之间。建树的方式还是使用建图的方式。 两个基本模型 树的最长路径：即所有节点的子路径的最大值加次大值的最大值 int dfs(int u,int father){ int dist = 0; int d1 = 0,d2 = 0; for (int i = h[u];i != -1;i = ne[i]){ int j = e[i]; if (j == father) continue; ...

POJ3304 大致题意 给定个线段，求是否存在一条直线，所有的线段在该直线上的投影都有一个公共点。 思路 题目可以转化为，是否存在一条直线可以穿过所有的线段。我们可以将所有的线段的两个端点全部存在一个数组里，任取两个不同的点构成直线，判断这条直线是否穿过所有线段。如果有一条这样的线段存在就输出Yes!，否则输出No!直线穿过线段可以使用向量和点的有向面积来判断。 代码 #include <iostream> #include <cstring> #include <cmath> #include <algorithm> using names...

POJ2318 大致题意 给定一个矩阵的四个顶点坐标，和矩阵内的条直线和个点，求每个被直线分成的区域内各包含多少点 思路 对于条边，我们通过二分查找到当前点右边的第一条边（因为点不可能存在于边上）就是该点所存在的区域。我们可以通过这个点和边的有向面积的正负判断点在线段的哪个方位。 代码 #include <iostream> #include <vector> #include <algorithm> #include <utility> using namespace std; typedef long long LL; typedef un...

简单总结 几何最重要的计算单位就是向量，可以使用pair<>来定义变量，或者自定义结构体（需要重载一些运算符） 向量最重要的两个操作 点积，用来计算向量夹角 叉积，用来计算面积（方向性面积），通过不同点和一个线段的面积的正负可以判断这个点的相对直线的位置 向量的旋转也是比较重要的内容 浮点数判断正负使用sign函数，比较大小使用cmp函数，依据题目确定eps的大小 1. 前置知识点 (1) pi = acos(-1); (2) 余弦定理 c^2 = a^2 + b^2 - 2abcos(t) 2. 浮点数的比较 const double eps = 1...

区间DP的总结和整理 基本思路 确定状态表示，即表示的状态是什么 确定划分依据，即的含义和取值（是否能取到L或者R） 基本框架（枚举区间长度和左端点，并确定右端点，通过k进行转移） for (int len = 2;len <= n;++len){ for (int i = 1;i + len - 1 <= n;++i){ int r = i + len - 1;int l = i; f[l][r] = INF; for (int k = l;k < r;++k) f[l][r] = min...

状态压缩DP 棋盘类 即对于地图类的问题，当前行只受上一行或者前两行的影响，而不受其他因素的影响，此时可用状态压缩DPAcwing1064 小国王 只受上一行影响 #include <bits/stdc++.h> using namespace std; const int N = 12,M = 1 << 10, K = 110; typedef long long LL; int n,m; vector<int> state; vector<int> head[M]; int cnt[M]; LL f[N][K][M]; /...