刚接触一点计算几何，就把一些知识点记录在这里，后面会不断补充。
这两个东西都可以用一对 double 来表示且运算基本相同，于是就放在一起。
0.储存
1 | struct Vector |
1.加
1 | Vector add(Vector a, Vector b) |
2.减
1 | Vector add(Vector a, Vector b) |
3.点积
1 | double dot(Vector a, Vector b) |
4.叉积
1 | double cross(Vector a, Vector b) |
0.储存
1 | struct Line |
1.跨立实验
2.李超线段树 算法：用线段树标记永久化维护平面内线段覆盖情况
1 | //维护线段的下凸壳 |
1.多边形面积 算法：取一点进行三角形剖分，然后用叉积求出三角形面积
1 | double area() |
2.凸包 性质：所有邻边的叉积符号相同 算法：Graham扫描法
1 | void Graham() |
11月15日 Educational Codeforces Round 56 题目链接：https://codeforces.com/contest/1093
思路： 一个简单的计数题。
首先根据题意可以得知，一条边两端的奇偶性一定要是不同的，因此只有二分图是存在可行方案的。考虑计数，先二分图染色（假设染成黑白两色），那么对于每一个连通块可行的方案就是 $2^{白色点数}+2^{黑色点数}$，然后总方案就是每个连通块方案的乘积。
代码：
1 | #include <cstdio> |
思路： E 题就是个这么毒瘤的数据结构。。正解似乎是树套树，但是 CDQ 显然能做。
先可以将问题转化一下，处理出数组 $b$ 中的数字在数组 $a$ 中的位置记为数组 $c$，那么询问操作就是询问 $c[lb~rb]$ 中有多少个数的值在 $la~ra$ 内。这是一个二维数点问题，可以使用树状数组维护，由于有修改操作，那么就用 CDQ 基于时间一维进行分治就好了。时间复杂度也是 $O((n+m)log^2n)$。
代码：
1 | #include <cstdio> |
思路： 是一个很有趣的 DP。
如果不考虑限制可以得到转移：$f[i][j]=\sum_{x=1}^{k} f[i-1][x]$，其中如果 $a[i]=-1$ 那么 $j$ 可以取 $1~k$ 所有数，否则 $j$ 只能取 j。接下来就是要把不合法的状态减去，我们记录一个数组 $pre[i]$ 表示从下标 $pre[i]$ 开始全可以取数字 $i$，由此我们就可以判断一个状态是否合法。如果数字 $j$ 在位置 $i$ 上不合法，那么我们就应该减去 $\sum_{x!=j} f[i-len][x]$。
代码：
1 | #include <cstdio> |
思路： G 题与 E 题比反而是一个比较简单的数据结构题。
考虑 $k$ 比较小，于是我们可以对一个点枚举在每一维上对答案的贡献情况，即在公式 $\sum \limits_{i = 1}^{k} |a_{x, i} - a_{y, i}|$ 去掉绝对值时的符号。对于我们枚举的每一种情况，由于去掉了绝对值，答案便是求一个区间内最大值与最小值之差，这个可以很简单的用线段树去维护。
为了减小码量，对于每一棵线段树可以只维护最小值。而最大值与最小值之差就是当前状态下的最小值与相反状态下最小值的和。
代码：
1 | Copy |
windy 定义了一种 windy 数。不含前导零且相邻两个数字之差至少为 2 的正整数被称为 windy 数。windy 想知道在 A 和 B 之间（包括 A 和 B）总共有多少个 windy 数？
包含两个整数，A B。
一个整数，同题目要求
一个比较简单的数位DP吧，直接按照套路来就好了。$f[i][j]$ 表示在第 $i$ 位上为 $j$ 的可能情况数，利用 $f$ 数组记忆化。然后需要注意的是，处理前导零时也不能够记忆化（仅针对我这种写法）。
1 | #include <cstdio> |
Tehran 的一家每天 $24$ 小时营业的超市，需要一批出纳员来满足它的需要。超市经理雇佣你来帮他解决问题——超市在每天的不同时段需要不同数目的出纳员为顾客提供优质服务。他希望雇佣最少数目的出纳员。
经理已经提供给你一天的每一小时需要出纳员的最少数量——$R(0),R(1),⋯,R(23)$。表示从午夜到上午 $0:00$ 需要出纳员的最小数目，每一天，这些数据都是相同的。有 $N$ 人申请这项工作，每个申请者 $i$ 在每 $24$ 小时中，从一个特定的时刻开始连续工作恰好 $8$ 小时。定义 $t_i$ 为上面提到的开始时刻。也就是说，如果第 $i$ 个申请者被录取，他将从 $t_i$ 时刻开始连续工作 $8$ 小时。
第一行为测试点的数目 $T$。
对于每组测试数据，第一行为 $24$ 个整数，表示 $R(0),R(1),R(2),⋯ ,R(23)$ 接下来一行一个正整数 $N$，表示申请者数目； 接下来 $N$ 行每行一个整数 $t_i$
对于每个测试点，输出一行，包含一个整数，表示需要出纳员的最小数目。如果无解，输出 No Solution。
一道差分约束很好的例题。本题思路引用了 这篇 Discuss
首先考虑约束关系。设：$r_i$ 为时间 $i$ 需要的人数 $t_i$ 为时间 $i$ 应聘的人数 $s_i$ 为时间 $i$ 以及之前录用的人数和
那么就存在约束关系： $s_i-s_{i-8}\geq r_i (8\leq i\leq 24)$ $s_i-s_{16+i}\geq r_i-s_{24} (1\leq i\leq 7)$ $s_i-s_{i-1}\geq 0 (1\leq i\leq 24)$ $s{i-1}-s_i\geq -t_i (1\leq i\leq 24)$
1 | #include <cstdio> |
$n$只奶牛构成了一个树形的公司，每个奶牛有一个能力值$p_i$，$1$号奶牛为树根。问对于每个奶牛来说，它的子树中有几个能力值比它大的。
第一行一个整数$n$，表示有$n$头奶牛 接下来$n$行为$1-n$号奶牛的能力值$p_i$ 接下来$n-1$行为$2-n$号奶牛的经理（树中的父亲）
共$n$行，每行输出奶牛$i$的下属中有几个能力值比$i$大
其实看完题后第一反应是树上启发式合并（不过应该可做，这种方法先坑着）。既然这是线段树合并的模版，那么还是先用这种方法做一遍吧。
首先离散化，然后对于每一个节点都建一颗权值线段树（里面都只有一个节点），接着dfs一遍，将每个节点儿子的线段树并在该节点上，然后跟新这个节点的答案就好了。
不过合并的操作复杂度是取决于线段树重合部分的大小，空间也要开很多倍。
1 | #include <cstdio> |