算法模版(C Version)

2024-09-15

基础数据结构

二分搜索

二分有两种实现方式，根据不同的判断条件给出不同的实现方式：

int bin1(int l, int r) {
    while(l < r) {
        int mid = (l + r + 1) >> 1;
        if(check()) r = mid - 1;
        else l = mid;
    }
    return l;
}

int bin2(int l, int r) {
    while(l < r) {
        int mid = (l + r) >> 1;
        if(check()) r = mid;
        else l = mid + 1;
    }
    return l;
}

另外，假设数组为非严格递增给出类似 lower_bound 的实现方式：

int lower_bound(int *arr, int l, int r, int num, int greater) {
    if(greater && arr[r] < num) return r + 1;
    if(!greater && arr[r] > num) return r + 1;
    while(l < r) {
        int mid = (l + r) >> 1;
        if(greater) {
            if(arr[mid] < num) l = mid + 1;
            else r = mid;
        } else {
            if(arr[mid] > num) l = mid + 1;
            else r = mid;
        }
    }
    return l;
}

如果数组非严格递增，则有：

查找数组中第一个大于等于 $num$ 的数: lower_bound(arr, 1, n, num, 1)
查找数组中第一个大于 $num$ 的数：lower_bound(arr, 1, n, num+1, 1)

如果数组非严格递减，则有：

查找数组中第一个小于等于 $num$ 的数：lower_bound(arr, 1, n, num, 0)
查找数组中第一个小于 $num$ 的数： lower_bound(arr, 1, n, num-1,0)

堆

给出大根堆的实现方式：

#define maxn 100005
#define fa(x) (x >> 1)
#define ls(x) (x << 1)
#define rs(x) (x << 1 | 1)
#define swap(x, y) ((*x) ^= (*y) ^= (*x) ^= (*y))

int tree[maxn], sz;
void insert(int x) {
    tree[++sz] = x; int p = sz;
    while(fa(p) && tree[p] > tree[fa(p)]) {
        swap(&tree[p], &tree[fa(p)]); 
        p = fa(p);
    }
}

void pop() {
    tree[1] = tree[sz--]; int p = 1;
    while(ls(p) <= sz) {
        int son = ls(p);
        if(rs(p) <= sz && tree[rs(p)] > tree[son]) son = rs(p);
        if(tree[son] > tree[p]) swap(&tree[son], &tree[p]);
        p = son;
    }
}

同理，如果实现一个可删堆的话，只需要另外再建一个最小堆维护需要删除的元素即可。这里需要注意的是输出的时候要先判断是否需要删除，删除之后判断是否为空再输出。

归并

以归并排序为例：

void mergeSort(int *arr, int begin, int end) {
    if(begin >= end) return;
    int mid = (begin + end) >> 1;
    mergeSort(arr, begin, mid);
    mergeSort(arr, mid + 1, end);

    int l = begin, r = mid + 1, top = begin;
    while(l <= mid && r <= end) {
        if(arr[l] <= arr[r]) b[top++] = arr[l++];
        else b[top++] = arr[r++];
    }
    while(l <= mid) b[top++] = arr[l++];
    while(r <= end) b[top++] = arr[r++];

    for(int i = begin; i <= end; i++) arr[i] = b[i];
}

排序

在此主要说明 qsort 排序：

//void qsort(void *base, size_t nitems, size_t size, int (*compar)(const void *, const void*));
qsort(arr, n, sizeof(arr[0]), cmp);

int cmp(const void *a, const void *b) {
    int p1 = *(int *)a, p2 = *(int *)b;
    return p1 > p2;   // p1 - p2 从小到大排序，注意返回值为 int 不要溢出
}

string.h 库函数

注意最后操作完要在最后面补一个 \0 !

// 将字符串str2复制到字符串str1中，并覆盖str1原始字符串，可以用来为字符串变量赋值
strcpy(str1,str2);
// 将字符串str2中的前n个字符复制到字符串str1的前n个字符中
strncpy(str1,str2,n);
// 将字符串str2添加到字符串str1的尾部，也就是拼接两个字符串
strcat(str1,str2);
// 将字符串str2的前n个字符添加到字符串str1的尾部
strncat(str1,str2,n);
// 比较两个字符串，如果相等，则返回0；若str1大于str2 返回一个正数（这个正数不一定是1）；若str1小于str2，返回一个负数（不一定是-1）
strcmp(str1,str2);
// 比较两个字符串的前n个字符
strncmp(str1,str2,n);
// 在str字符串中查找首次出现字符c的位置（从字符串的首地址开始查找）
strchr(str,c);
// 在字符串str中从后向前开始查找字符c首次出现的位置
strrchr(str,c);
// 在字符串str1中查找字符串str2的位置，若找到，则返回str2第一个字符在str1中的位置的指针，若没找到，返回NULL
strstr(str1,str2);
// 字符串转换到 int, double, long long
atoi(str); atof(str); atol(str);

ctype.h 库函数

函数名	主要功能
isalnum(ch)	检查 ch 是否为字母或数字
isalpha(ch)	检查 ch 是否为字母
iscntrl(ch)	检查 ch 是否为控制字符(ASCII值在 0 ~ 31)
isdigit(ch)	检查 ch 是否为数字(‘0’ ~ ‘9 ‘)
islower(ch)	检查 ch 是否为小写字母(‘a’ ~ ‘z’)
tolower(ch)	将 ch 字符转换成小写字母
isspace(ch)	检查 ch 是否为 ’ ‘, ‘\t’, ‘\n’, ‘\v’, ‘\f’, ‘\r’

ST 表

ST 表常用来解决 RMQ 问题，是用于解决 可重复贡献问题 的数据结构。

可重复贡献问题是指对于运算 opt, 满足 $ x \ opt \ x=x$ , 则对应的区间询问就是一个可重复贡献问题。例如, 最大值有 $ \max (x, x)=x$, $ \operatorname{gcd} $ 有 $ \operatorname{gcd}(x, x)=x$ ，所以 RMQ 和区间 GCD 就是一个可重复贡献问题。像区间和就不具有这个性质, 如果求区间和的时候采用的预处理区间重叠了, 则会导致重叠部分被计算两次, 这是我们所不愿意看到的。另外, opt 还必须满足结合律才能使用 ST 表求解。

记 f[i][j] 表示区间 $[i, i + 2^j - 1]$ 内的最大值，初始条件有 $f[i][0] = a[i]$。

#define logn 21

for (int j = 1; j <= logn; j++)
    for (int i = 1; i + (1 << j) - 1 <= n; i++)
      f[i][j] = max(f[i][j - 1], f[i + (1 << (j - 1))][j - 1]);

查询区间 $[l, r]$ 内的最值时，将其划分为两个区间查询即可：

void pre() {  // logn[i] 表示 log_2 x <= i 的最大 x 数值
  Logn[1] = 0; Logn[2] = 1;
  for (int i = 3; i < maxn; i++)
    Logn[i] = Logn[i / 2] + 1;
}

int query(int l, int r) {
  int s = Logn[r - l + 1];
  return max(f[x][s], f[y - (1 << s) + 1][s]);
}

树状数组

树状数组是一种支持 单点修改 和 区间查询 的代码量小的数据结构。

#define maxn 100005
int c[maxn];

int lowbit(int x) {return x & -x;}

void add(int x, int k) {  // 修改 a[x]
  while (x < maxn) {
    c[x] = c[x] + k;
    x = x + lowbit(x);
  }
}

int query(int x) {  // a[1]..a[x]的和
  int ans = 0;
  while (x > 0) {
    ans = ans + c[x];
    x = x - lowbit(x);
  }
  return ans;
}

线段树

线段树是算法竞赛中常用的用来维护 区间信息 的数据结构。

线段树可以在 $O(log N)$ 的时间复杂度内实现单点修改、区间修改、区间查询（区间求和，求区间最大值，求区间最小值)等操作。以下给出区间修改区间查询的基础板子。

#define maxn 100005
#define fa(x) (x >> 1)
#define ls(x) (x << 1)
#define rs(x) (x << 1 | 1)
typedef long long ll;

int tag[maxn << 2];
ll o[maxn << 2], a[maxn];

// 一次性输入后建树
void build(int idx, int l, int r) {
 if(l == r) {o[idx] = a[l]; return;}
	
	int mid = (l + r) >> 1;
	build(ls(idx), l, mid);
	build(rs(idx), mid + 1, r);
	o[idx] = o[ls(idx)] + o[rs(idx)];
}

void update(int idx, int l, int r, int k) {
	o[idx] += (r - l + 1) * k;
	tag[idx] += k;
}

void push(int idx, int l, int r) {
	if(tag[idx]) {
		int mid = (l + r) >> 1;
		update(ls(idx), l, mid, tag[idx]);
		update(rs(idx), mid + 1, r, tag[idx]);
		tag[idx] = 0;
	}
}

// 向 [addL, addR] 区间中每个点加 k
void add(int idx, int l, int r, int k, int addL, int addR) {
	if(addL <= l && addR >= r) {
		o[idx] += (r - l + 1) * k;
		tag[idx] += k;
		return;
	}
	
	push(idx, l, r);
	int mid = (l + r) >> 1;
	if(addL <= mid) add(ls(idx), l, mid, k, addL, addR);
	if(addR > mid) add(rs(idx), mid + 1, r, k, addL, addR);
	o[idx] = o[ls(idx)] + o[rs(idx)];
}


// 查询 [QL, QR] 区间和
ll query(int idx, int l, int r, int QL, int QR) {
	if(QL <= l && QR >= r) return o[idx];
	
	ll ans = 0;
	int mid = (l + r) >> 1;
	push(idx, l, r);
	if(QL <= mid) ans += query(ls(idx), l, mid, QL, QR);
	if(QR > mid) ans += query(rs(idx), mid + 1, r, QL, QR);
	return ans; 
}

数学相关

欧几里得

求最大公因数：

int gcd(int a, int b) {return b == 0 ? a : gcd(b, a%b);}

扩展欧几里得求解 ax + by = c 的不定方程：

void ex_gcd(int a, int b, int *gcd, int *x, int *y) {
    if(!b) {*gcd = a; *x = 1; *y = 0;}
    else {
        ex_gcd(b, a%b, gcd, y, x); // x 和 y 的顺序互换
        (*y) -= (*x) * (a / b);
    }
}

最后给出通解：

$$ \left\{\begin{array}{l} x=x_{0}+k \frac{b}{\operatorname{gcd}(a, b)} \\ y=y_{0}-k \frac{a}{\operatorname{gcd}(a, b)} \end{array}\right. $$

线性筛

#define MAXN 1000006
int prime[MAXN], vis[MAXN], top = 0;
void ask_prime(int end) {
    for(int i = 2; i <= end; i++) {
        if(!vis[i]) prime[++top] = i;
        for(int j = 1; j <= top && i * prime[j] <= end; j++) {
          vis[i * prime[j]] = true;
          if(i % prime[j] == 0) break;
        }
    }    
}

快速幂

ll fpm(ll a, ll b) {  // a^b
    ll res = 1;
    for(; b; b >>= 1, a = (a * a) % MOD) 
        if(b&1) res = (res * a) % MOD;
    return res;
}

求逆元

模数为质数

此时可以使用费马小定理： $a x \equiv 1(\bmod b)$ 可以得逆元 $x \equiv a^{b-2} (\bmod b)$

模数为合数

此时相当于求解 $a x \equiv 1(\bmod b)$ 转换为：$ax + by = 1$ ，扩欧求解 $x$ 即可。

线性求逆元

inv[1] = 1;
for (int i = 2; i <= n; ++i) 
  inv[i] = (long long)(p - p / i) * inv[p % i] % p;

组合数

$$ C^m_n = \frac{n!}{m!(n-m)!} \quad A^m_n = \frac{n!}{m!} \\ C^m_n = C^m_{n-1} + C^{m-1}_{n-1} \\ C^{m+1}_n = \frac{n-m}{m+1}C^m_n \\ C^m_n \bmod p = C^{m \% p}_{n \% p} \times C^{m / p}_{n / p} \bmod p \ (\text{p is a prime number}) $$

long long Lucas(long long n,long long m){
    if(m==0)  return 1;
    return Lucas(n/p,m/p)*C(n%p,m%p)%p;
}

int C(int m, int n) {
  ans = 1;
  for(int i = 1; i <= m; i++) ans = ans * (n - i + 1) / i;
  return ans;
}

动态规划

最长公共子序列

考虑两个串 s,t 的最长公共子序列，记 dp[i][j] 表示只考虑 s[1～i] 和 t[1～j] 时的最长公共子序列长度，有转移方程：

$$ dp[i][j] = \begin{cases} dp[i-1][j-1] + 1 & s[i] = t[j] \\ \max(dp[i][j-1], dp[i-1][j]) & \text{else} \end{cases} $$

如果需要输出转移路径时不可以直接通过值之间的关系跳转，需要标记转移位置：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define maxn 1003
#define max(a, b) ((a) > (b) ? (a) : (b))

int dp[maxn][maxn],road[maxn][maxn], pos;
char s[maxn], t[maxn], str[maxn];

int main()
{
#ifdef LOCAL
    freopen("1.in", "r", stdin);
#endif
    
    scanf("%s%s", s + 1, t + 1);
    int sl = strlen(s + 1), tl = strlen(t + 1);

    for(int i = 1; i <= sl; i++) for(int j = 1; j <= tl; j++) {
        if(s[i] == t[j]) dp[i][j] = dp[i - 1][j - 1] + 1, road[i][j] = 1;
        else dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
    }
 
    int x = sl, y = tl;
    while(x && y && dp[x][y]) {
        if(dp[x][y] == dp[x-1][y-1] + 1 && road[x][y]) 
          str[dp[x][y]] = s[x], --x, --y; 
        else if(dp[x][y] == dp[x][y-1]) --y;
        else --x;
    }
    printf("%s\n", str + 1);
    return 0;
}

最长上升子序列

给出一个 O(nlogn) 的做法：

设数组 dp[i] 表示上升子序列长度为 i 时，最后一个元素的最小值，很明显该数组递增。由此可以更新：

int ans = 0;
for(int i = 1; i <= n; i++) {
  if(a[i] >= dp[ans]) dp[++ans] = a[i];
  else {
    int p = lower_bound(dp, 1, ans, a[i], 1);
    dp[p] = a[i];
  }
}
// the answer is ans

图论

最短路

	`Floyd`	`Dijkstra`	`Bellman-Ford`
空间复杂度	$O(N^2)$	$O(M)$	$O(M)$
时间复杂度	$O(N^3)$	$O((M+N)logN)$	最坏$O(MN)$
负权边	可以处理	不能处理	可以处理
判定是否存在负权回路	不能	不能	能判定

floyd 最短路

考虑使用每个点对每一条边进行松弛，循环顺序最好别互换；

#define FOR(i, a, b) for(int i = a; i <= b; i++)

FOR(k, 1, n) FOR(i, 1, n) FOR(j, 1, n) 
        dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);

Dijkstra 单源最短路

#include <stdio.h>

#define maxn 1000006
#define maxm 1600006
#define fa(x) (x >> 1)
#define ls(x) (x << 1)
#define rs(x) (x << 1 | 1)
#define inf 0x3f3f3f3f3f3f3f3f
#define min(a, b) ((a) < (b) ? (a) : (b))
#define FOR(i, a, b) for(int i = a; i <= b; i++)
#define swap(x, y) ((*x) ^= (*y) ^= (*x) ^= (*y))

typedef long long ll;
typedef struct node {
    int v, nex, w;
}node;

node edge[maxm * 2];
int G[maxn], vis[maxn], tot, sz;
ll dis[maxn], tr[maxm];

void add(int u, int v, int w) {
    edge[++tot].v = v; edge[tot].w = w;
    edge[tot].nex = G[u]; G[u] = tot;
}

void insert(int x) {
    tr[++sz] = x; int p = sz;
    while(fa(p) && dis[tr[fa(p)]] > dis[tr[p]]) {
        swap(&tr[fa(p)], &tr[p]);
        p = fa(p);
    }
}

void pop() {
    tr[1] = tr[sz--]; int p = 1;
    while(ls(p) <= sz) {
        int son = ls(p);
        if(rs(p) <= sz && dis[tr[rs(p)]] < dis[tr[ls(p)]]) son = rs(p);
        if(dis[tr[son]] < dis[tr[p]]) swap(&tr[son], &tr[p]);
        else break;
        p = son;
    }
}

ll Dijkstra(int s, int t) {
    dis[s] = 0; insert(s);
    while(sz) {
        int u = tr[1]; pop();
        if(vis[u]) continue;
        vis[u] = 1;
        for(int i = G[u]; i; i = edge[i].nex) {
            int v = edge[i].v, w = edge[i].w;
            if(dis[v] > dis[u] + (ll)w) {
                dis[v] = dis[u] + (ll)w;
                insert(v);
            }
        }
    }
    return dis[t];
}

int main()
{
#ifdef LOCAL
    freopen("in.txt", "r", stdin);
#endif

    int n, m, s, t; scanf("%d%d%d%d", &n, &m, &s, &t);
    FOR(i, 1, m) {
        int u, v, w; scanf("%d%d%d", &u, &v, &w);
        if(u == v) continue;
        add(u, v, w); add(v, u, w);  // 无向图
    }
    FOR(i, 1, n) dis[i] = inf;
    printf("%lld\n", Dijkstra(s, t));
    return 0;
}

Bellman-ford 判断负环

核心思路是最短路最多松弛 n-1 次，时间复杂度 O(mn)。

#include <stdio.h>

#define maxn 2003
#define maxm 6003
#define inf 1000000000
#define min(a, b) ((a) < (b) ? (a) : (b))

typedef struct node {
    int u, v, w;
}node;
node edge[maxm];

int dis[maxn];

int main()
{
#ifdef LOCAL
    freopen("in.txt", "r", stdin);
#endif

    int tt; scanf("%d", &tt);
    while(tt--) {
        int n, m; scanf("%d%d", &n, &m);
        for(int i = 1; i <= m; i++) 
            scanf("%d%d%d", &edge[i].u, &edge[i].v, &edge[i].w);
        
        for(int i = 1; i <= n; i++) dis[i] = inf;
        dis[1] = 0;

        for(int i = 1; i < n; i++) for(int j = 1; j <= m; j++)
            dis[edge[j].v] = min(dis[edge[j].v], dis[edge[j].u] + edge[j].w);
        
        int flag = 0;
        for(int i = 1; i <= m; i++) 
          if(dis[edge[i].v] > dis[edge[i].u] + edge[i].w)
            {flag = 1; break;}
        
        if(flag) printf("boo how\n");
        else {for(int i = 1; i <= n; i++) printf("%d%c", dis[i], " \n"[i == n]);}
    }
    return 0;
}

SPFA 模板

可以用于求解带负权边的单源最短路。

思路：尝试利用每一条边进行松弛，一共需要松弛 n-1 轮即可达到最短路。再进一步考虑，每次其实只有松弛过的点所连的边才会继续松弛。

int dis[N];  // 用于记录最短距离
bool vis[N]; // 用于记录哪些点在队列里

void SPFA(int s) {
    memset(dis, 0x3f, sizeof(dis));
    memset(vis, false, sizeof(vis));
    queue<int> q;   q.push(s);  
    vis[s] = true;  dis[s] = 0;
    while(!q.empty()) {
        int u = q.front();  q.pop();
        vis[u] = false;
        for(int e = head[u]; e != 0; e = edge[e].nex) {
            int v = edge[e].to, w = edge[e].val;
            if(dis[u] + w < dis[v]) {
                dis[v] = dis[u] + w;
                if(vis[v] == false) {
                    q.push(v);
                    vis[v] = true;
                }
            }
        }
    }
}

当然使用该方法可以判断是否存在负环。如果发现一个点在队列里出现了 n 次则表明一定存在负环。

注意：以 s 点为源点跑该算法时，如果没有给出存在负环的结果，只能说明从该点出发不能抵达一个负环，而不能说明图上不存在负环。因此如果需要判断整个图上是否存在负环，最严谨的做法是建立一个超级源点，向图上每个节点连一条权值为 0 的边，然后以超级源点为起点执行算法。

Kruskal 最小生成树

注：只有连通图才有生成树，非连通图只有生成森林。

#include <stdio.h>

#define maxn 200005
#define maxm 500005
#define FOR(i, a, b) for(int i = a; i <= b; i++)
typedef long long ll;
typedef struct node {
    int u, v, w;
}node;
node edge[maxm];

int fa[maxn];
int findF(int x) {
    if(fa[x] != x) fa[x] = findF(fa[x]);
    return fa[x];
}

int cmp(const void *a, const void *b) {return ((node*)a)->w > ((node*)b)->w;}

ll Kruskal(int n, int m) {
    ll ans = 0, tot = 0;
    FOR(i, 1, m) {
        int u = edge[i].u, v = edge[i].v, w = edge[i].w;
        int uf = findF(u), vf = findF(v);
        if(uf != vf) {
            tot++; ans += (ll)w;
            fa[uf] = vf;
            if(tot == n - 1) break;
        }
    }
    return ans;
}

int main()
{
#ifdef LOCAL
    freopen("in.txt", "r", stdin);
#endif

    int n, m; scanf("%d%d", &n, &m);
    FOR(i, 1, n) fa[i] = i;
    FOR(i, 1, m) scanf("%d%d%d", &edge[i].u, &edge[i].v, &edge[i].w);
    qsort(edge + 1, m, sizeof(node), cmp);

    printf("%lld\n", Kruskal(n, m));
    return 0;
}

拓扑排序

对有向图而言，需要记录每个点的入度，然后开一个队列维护入度为零的点即可。

#include <stdio.h>

#define maxn 100005
#define maxm 200005
#define fa(x) (x >> 1)
#define ls(x) (x << 1)
#define rs(x) (x << 1 | 1)
#define FOR(i, a, b) for(int i = a; i <= b; i++)
#define swap(x, y) ((*x) ^= (*y) ^= (*x) ^= (*y))

typedef struct node {
    int v, nex;
} node;
node edge[maxm * 2];
int deg[maxn], G[maxn], que[maxn], pos, __beg, __end;

void add(int u, int v) {
    edge[++pos].v = v; edge[pos].nex = G[u];
    G[u] = pos;
}

void init() {__beg = 0; __end = 0;}
int qlen() {return __end - __beg;}
void pop() {__beg++;}
int front() {return que[__beg];}
void push(int x) {que[__end++] = x;}

int main()
{
#ifdef LOCAL
    freopen("in.txt", "r", stdin);
#endif

    int tt; scanf("%d", &tt);
    while(tt--) {
        int n, m; scanf("%d%d", &n, &m);
        FOR(i, 1, n) deg[i] = 0, G[i] = 0;
        pos = 0;
        FOR(i, 1, m) {
            int u, v; scanf("%d%d", &u, &v);
            add(u, v); deg[v]++;
        }

        init();
        FOR(i, 1, n) if(!deg[i]) push(i);
        while(qlen() == 1) {
            int u = front(); pop();
            for(int i = G[u]; i; i = edge[i].nex) {
                int v = edge[i].v;
                deg[v]--;
                if(deg[v] == 0) push(v);
            }
        }
        if(__end == n && !qlen()) puts("yy");
        else puts("nn");
    }
    return 0;   
}

最小环

全局最小环—Floyd

思路：

记原图中 u, v 之间边的边权为 val(u, v)。

我们注意到 Floyd 算法有一个性质：在最外层循环到点 k 时（尚未开始第 k 次循环），最短路数组 dis 中，dis(u,v) 表示的是从 u 到 v 且仅经过编号在 $[1,k)$ 区间中的点的最短路。

由最小环的定义可知其至少有三个顶点，设其中编号最大的顶点为 w ，环上与 w 相邻两侧的两个点为 u, v ，则在最外层循环枚举到 k = w 时，该环的长度即 dis(u,v) + val(v, w) + val(w, u)。

故在循环时对于每个 k 枚举满足 i,j < k 的节点 (i,j)，更新答案即可。

LL res = INF;	
for(int k = 1; k <= n; ++k) {
    for(int i = 1; i < k; ++i)
        for(int j = 1; j < i; ++j) 
            res = min(res, dis[i][j] + graph[k][i] + graph[j][k]);
    for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= n; ++j)
            dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
}

最短路树

求正权单源最短路之后满足 dist(u)+val(u,v)=dist(v) 的边 (u,v) 构成的以起点为根的树。

如果想求经过节点 i 的最小环：

首先以 i 为根建立最短路树(Dijkstra 可建)
然后枚举非树边更新最小环即可。

int fa[N];  // 用于标记最短路树中的不同分叉

void Dijkstra(int s) {
    static priority_queue<PII, vector<PII>, greater<PII> > q;
    dis[s] = 0; q.push(MK(dis[s], s));
    while(!q.empty()) {
        int u = q.top().second; q.pop();
        if(vis[u]) continue;
        vis[u] = true;
        for(int e = head[u]; e != -1; e = edge[e].nex) {
            int v = edge[e].to;
            if(dis[v] > dis[u] + edge[e].val) {
                dis[v] = dis[u] + edge[e].val;
                if(u == s) fa[v] = v;
                else fa[v] = fa[u];
                q.push(MK(dis[v], v));
            }
        }
    }
}

Dinic 网络流

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#define maxn 105
#define maxm 5003
#define inf 0x3f3f3f3f3f3f3f3f
#define min(a, b) ((a) < (b) ? (a) : (b))

typedef long long ll;

typedef struct node {
    ll v, nex, w;
}node;
node edge[maxm << 1];
int G[maxn], cur[maxn], pos;

void add(int u, int v, int w) {
    edge[++pos].v = v; edge[pos].w = w;
    edge[pos].nex = G[u]; G[u] = pos;
}

int level[maxn];
int __begin__, __end__, que[maxn];
void qinit() {__begin__ = 0; __end__ = 0;}
void push(int x) {que[__end__++] = x;}
void pop() {__begin__++;}
int front() {return que[__begin__];}
int qlen() {return __end__ - __begin__;}

int bfs(int s, int t) {
    memset(level, 0, sizeof(level));
    memcpy(cur, G, sizeof(G));
    qinit(); push(s); level[s] = 1;
    while(qlen()) {
        int u = front(); pop();
        for(int i = G[u]; i; i = edge[i].nex) {
            ll v = edge[i].v, flow = edge[i].w;
            if(flow > 0 && level[v] == 0) {
                level[v] = level[u] + 1;
                push(v);
            }
        }
    }
    return (level[t] != 0);
}

ll dfs(int s, int t, ll limit) {
    if(s == t) return limit;
    ll ret = 0;
    for(int i = cur[s]; i; i = edge[i].nex) {
        cur[s] = i;
        ll v = edge[i].v, vol = edge[i].w;
        if(level[v] == level[s] + 1 && vol > 0) {
            ll f = dfs(v, t, min(limit - ret, vol));
            edge[i].w -= f;
            edge[i^1].w += f;
            ret += f;
            if(ret == limit) return limit;
        }
    }
    return ret;
}


ll Dinic(int s, int t) {
    ll max_flow = 0;
    while(bfs(s, t)) max_flow += dfs(s, t, inf);
    return max_flow;
}

int main()
{
#ifdef LOCAL
    freopen("in.txt", "r", stdin);
#endif

    int tt; scanf("%d", &tt);
    while(tt--) {
        pos = 1;  // 从 1 开始，方便异或操作(2-3, 4-5, ...)
        memset(G, 0, sizeof(G));
        int n, m, s, t; scanf("%d%d%d%d", &n, &m, &s, &t);
        for(int i = 1; i <= m; i++) {
            int u, v, w;    scanf("%d%d%d", &u, &v, &w);
            add(u, v, w); add(v, u, 0);  // 同时加反向边
        }
        printf("%lld\n", Dinic(s, t));
    }
    return 0;
}

二分图最大匹配匈牙利算法

n 个点和 n 个点进行匹配有：

#define maxn 100005
int mp[maxn][maxn], vis[maxn], p[maxn], n;

int match(int i) {
    for(int j = 1; j <= n; ++j) if(mp[i][j] && !vis[j]) {
        vis[j] = 1;
        if(p[j] == 0 || match(p[j])) {
            p[j] = i;
            return 1;
        }
    }
    return 0;
}

int Hungarian() {
    int cnt = 0;
    for(int i = 1; i <= n; i++) {
        memset(vis, 0, sizeof(vis));
        if(match(i)) cnt++;
    }
    return cnt;
}

连通性

强连通分量

强连通定义：有向图 G 强连通是指，G 中任意两个结点连通(可以相互到达)。

强连通分量定义：极大的强连通子图。

tarjan

思路：每个节点维护两个变量值：dfn 和 low ，分别代表遍历到该点的 dfs 序和能回到的最早的父节点。然后就 DFS 遍历即可。

int dfn[MAXN], low[MAXN], scc[MAXN], sz[MAXN]; // sz 储存每个强连通分量大小 
int sc = 0, dfncnt = 0;
bool in[MAXN];
stack<int> st;
void tarjan(int s) {
    dfn[s] = low[s] = ++dfncnt; st.push(s); in[s] = true;
    for(int e = head[s]; e != 0; e = edge[e].nex) {
        int v = edge[e].to;
        if(!dfn[v]) {
            tarjan(v);
            low[s] = min(low[s], low[v]);
        }
        else if(in[v])  low[s] = min(low[s], dfn[v]);
    }
    if(dfn[s] == low[s]) {
        ++sc;
        while(st.top() != s) {
            scc[st.top()] = sc; sz[sc]++;
            in[st.top()] = false;   st.pop();
        }
        scc[st.top()] = sc; sz[sc]++;
        in[st.top()] = false;   st.pop();
    }
}

2-SAT

原式	建图
$\neg a \vee b$	$(a \rightarrow b) \wedge (\neg b \rightarrow \neg a)$
$a \vee b$	$(\neg a \rightarrow b) \wedge (\neg b \rightarrow a)$
$\neg a \vee \neg b$	$(a \rightarrow \neg b) \wedge (b \rightarrow \neg a)$

转化后建立有向图，观察是否存在一个变量 x 使得 $x$ 和 $\neg x$ 在同一个强连通分量内即可。如果不存在则有解。此时观察 $x$ 和 $\neg x$ 所在的强连通分量编号，取较小值那个为真即可。

双联通分量

边双联通：在一张连通的无向图中，对于两个点 u 和 v，如果无论删去哪条边（只能删去一条）都不能使它们不连通，我们就说 u和 v 边双连通。（有传递性）
点双联通：在一张连通的无向图中，对于两个点 u 和 v，如果无论删去哪个点（只能删去一个且不能是 u 和 v）都不能使它们不连通，我们就说 u和 v 点双连通。（无传递性）

求割点

对于一个无向图，如果把一个点删除后这个图的极大连通分量数增加了，那么这个点就是这个图的割点（又称割顶）。

思路：依然进行 tarjan 搜索，如果一个节点 s 的儿子 v 有 low[v] >= dfn[s] 代表不经过节点 s 的话节点 v 无法到达上面的节点，则此时的 s 为割点。唯一需要注意的是起点需要特判一下(根据搜索树上儿子的数量)。

bool vis[MAXN], flag[MAXN];
int dfn[MAXN], low[MAXN], dfncnt = 0, sz = 0;
void tarjan(int s, int fa) {
    dfn[s] = low[s] = ++dfncnt; vis[s] = true;
    int child = 0;
    for(auto v : G[s]) {
        if(!vis[v]) {
            child++;
            tarjan(v, s);
            low[s] = min(low[s], low[v]);
            if(fa != s && low[v] >= dfn[s] && !flag[s]) {	// 判断情况
                sz++;
                flag[s] = true;
            }
        }
        else if(v != fa) low[s] = min(low[s], dfn[v]);	// 回到之前搜索过的节点
    }
    if(fa == s && child >= 2 && !flag[s]) {sz++; flag[s] = true;} // 特判起点

求割边

对于一个无向图，如果删掉一条边后图中的连通分量数增加了，则称这条边为桥或者割边。严谨来说，就是：假设有连通图$G = \{V, E\}$，$e$ 是其中一条边（即 $e \in E$），如果 $G - e$ 是不连通的，则边 $e$ 是图 $G$ 的一条割边（桥)。

思路：与割点差不多，只需修改为 low[u] > dfn[s] 即可(意味着该分支的节点全部最多回到 u，如果不通过 u 则不会回到其父节点 s，因此边 s-u 是一条割边)。且不用考虑根节点的问题。

int dfn[MAXN], low[MAXN], dfncnt = 0;
bool vis[MAXN];
void tarjan(int s, int fa) {
    dfn[s] = low[s] = ++dfncnt; vis[s] = true;
    for(auto v : G[s]) {
        if(!vis[v]) {
            tarjan(v, s);
            low[s] = min(low[s], low[v]); 
            if(low[v] > dfn[s])  // 只有一个判断条件
                bridge.push_back(make_pair(s, v));
        }
        else if(dfn[v] < dfn[s] && v != fa) // 这样多加一个判断也行，不加也行
            low[s] = min(low[s], dfn[v]);
    }
}

欧拉图

欧拉回路：通过图中每条边恰好一次的回路。
欧拉通路：通过图中每条边恰好一次的通路。
欧拉图：具有欧拉回路的图。
半欧拉图：具有欧拉通路但不具有欧拉回路的图。

性质：

欧拉图中所有顶点的度数都是偶数。

若 G 是欧拉图，则它可以被看作若干个环的并，且每条边被包含在奇数个环内。

判别法：

	无向图	有向图
欧拉图	1. 非零度顶点是连通的2. 顶点的度数都是偶数	1. 非零度顶点是强连通的2. 每个顶点的入度和出度相等
半欧拉图	1. 非零度顶点是连通的2. 恰有 2 个奇度顶点	1. 非零度顶点是弱连通的2. 至多一个顶点的出度与入度之差为 13. 至多一个顶点的入度与出度之差为 14. 其他顶点的入度和出度相等

FFT

给出计算大整数乘法的板子：

#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define PI acos(-1.0)
#define MAXN (1 << 21)
#define max(a, b) ((a) > (b) ? (a) : (b))

typedef long double LD;

struct C {
	double R,I;
}a[MAXN],b[MAXN];
void swapC(struct C *a,struct C *b)
	{struct C temp;temp=*a;*a=*b;*b=temp;}
struct C add(struct C *A,struct C *B)
	{return (struct C){A->R+B->R,A->I+B->I};}
struct C minus(struct C *A,struct C *B)
	{return (struct C){A->R-B->R,A->I-B->I};}
struct C multi(struct C *A,struct C *B)
	{return (struct C){A->R*B->R-A->I*B->I,A->R*B->I+A->I*B->R};}

int n1,n2,n,m,cnt,r[MAXN];

void init(){ //m为最高次数
	cnt = 0;
	for(n = 1; n <= m; n <<= 1) ++cnt;
	for(int i = 0; i < n; ++i) if(cnt)
        r[i] = (r[i >> 1] >> 1) | ((i & 1) << (cnt-1));
}

void FFT(struct C *a,int type){
	for(int i = 0; i < n; ++i)
		if(i < r[i]) swapC(&a[i], &a[r[i]]);
	for(int i = 2; i <= n; i <<= 1){
		struct C wn = (struct C) {cos(2*PI / i), sin(2*PI / i*type)};
		for(int j = 0; j<n; j += i) {
			struct C w = (struct C){1, 0};
			for(int k = 0; k < (i >> 1); ++k) {
				struct C x = a[j+k], y = multi(&a[j+k+(i >> 1)], &w);
				a[j+k] = add(&x,&y); 
                a[j+k+(i >> 1)] = minus(&x,&y);
				w = multi(&w,&wn);
			}
		}
	}
	if(type == -1) for(int i = 0; i<n; ++i) a[i].R /= n;
}


char sa[MAXN],sb[MAXN];
int ans[MAXN];

int main(){
#ifdef LOCAL
    freopen("in.txt", "r", stdin);
#endif

	int tt; scanf("%d", &tt); 
	while(tt--) {
		scanf("%s%s", sa, sb);
		n1 = strlen(sa), n2 = strlen(sb);
		m = n1 + n2 - 2; init();

		for(int i = 0; i < n; ++i) a[i] = b[i] = (struct C){0, 0};
		for(int i = 0; i < n1; ++i) a[i].R = sa[n1-1-i] - '0';
		for(int i = 0; i < n2; ++i) b[i].R = sb[n2-1-i] - '0';
		FFT(a,1); FFT(b,1);
		for(int i = 0; i < n; ++i) a[i] = multi(&a[i], &b[i]);
		FFT(a, -1);
		for(int i = 0; i < n + 50; ++i) ans[i]=0;
		int mx = 0;
		for(int i = 0; i < n; ++i){
			ans[i] += (int)(a[i].R + 0.5);
			int x = ans[i];
			ans[i] = 0;
			for(int c = i; x; x /= 10, ++c) {
				ans[c] += x % 10;
				mx = max(mx, c);
			}
		}
		for(int i = mx; i>=0; --i) printf("%d",ans[i]);
		puts("");
	}
	return 0;
}

字符串

KMP 字符串匹配

void KMP(char *s, char *t) {
  int lens = strlen(s), lent = strlen(t);
	for(int i = 1, j = 0; i < lent; nex[i++] = j) {
    while(j && t[i] != t[j]) j = nex[j - 1];
    if(t[i] == t[j]) j++;
	}

	for(int i = 0, j = 0; i < lens; i++) {
    while(j && s[i] != t[j]) j = nex[j - 1];
    if(s[i] == t[j]) j++;
    if(j == lent) printf("%d ", i + 1 - lent); // success
}

举例说明这里的 nex 数组， nex[i]严格定义为：该位置前面字符串的最长相同的真前缀和真后缀长度。

idx	0	1	2	3	4	5	6
str[]	a	b	a	b	c	a	a
nex[]	0	0	1	2	0	1	1

Mancher 最大回文串

举例，对字符串 aabbc 将被转换为 @#a#a#b#b#c#$ 来进行运算。

#define maxn 100005
char s[maxn << 1];

int Mancher(chsr *t) {
	int len = strlen(t), top = 0;
	s[top++] = '@';
	for(int i = 0; i < len; i++) s[top++] = '#', s[top++] = t[i];
	s[top++] = '#'; s[top++] = '$';

	int c, r = 0, ans = 0;
	for(int i = 1; i < top; i++) {
    if(r > i) p[i] = min(r - i, p[2 * c - i]);
    else p[i] = 1;
    while(s[i + p[i]] == s[i - p[i]]) p[i]++;
    if(p[i] + i > r) {
        r = p[i] + i; c = i;
        ans = max(ans, p[i]);
    }
	}
  return ans - 1; // 因为会多算一个 #
}

字符串哈希

给一个双哈希加拉链的实现方式：

#include <stdio.h>
#include <string.h>

#define MOD1 998244353
#define MOD2 1000000007
#define MOD3 100007
#define BASE1 307
#define BASE2 401
#define maxn 1000006

typedef long long ll;
typedef struct Pair {
	int x, y;
}Pair;

int G[MOD3], nex[maxn], e;
Pair val[maxn];

Pair hash(char *s, int len) {
	int x = 0, y = 0;
	for(int i = 0; i < len; i++) {
		x = ((ll)x * BASE1 + s[i]) % MOD1;
		y = ((ll)y * BASE2 + s[i]) % MOD2;
	}
	return (Pair){x, y};
}

int add(Pair v) {
	int u = v.x % MOD3;
	for(int i = G[u]; i; i = nex[i])
		if(val[i].x == v.x && val[i].y == v.y) 
			return 0;
	val[++e] = v; nex[e] = G[u]; G[u] = e;
	return 1;
}

char str[maxn];
int main()
{
#ifdef LOCAL
	freopen("in.txt", "r", stdin);
#endif

	int tt; scanf("%d\n", &tt);
	while(tt--) {
		scanf("%s", str);
		
	}
	return 0;
}

计算几何

Graham 求凸包

#include <stdio.h>
#include <math.h>

#define maxn 100005
#define eps 1e-9
#define max(a, b) ((a) > (b) ? (a) : (b))
#define MD(a, m) (a >= m ? (a - m) : (a))

typedef struct node {
    double x, y, ang;
}node;
node p[maxn];

node minus(node p1, node p2) {return (node){p1.x - p2.x, p1.y - p2.y};}

double cross(node p1, node p2) {return p1.x * p2.y - p1.y * p2.x;}
int dCmp(double x) {return fabs(x) < eps ? 0 : (x < 0 ? -1 : 1); }

double dis(node a, node b) {
    double xx = a.x - b.x, yy = a.y - b.y;
    return sqrt(xx * xx + yy * yy);
}

doubleline_dis(node a, node b, node x) {
    node line = minus(a, b), vec = minus(x, b);
    return fabs(line.x * vec.y - line.y * vec.x);
}

int cmp(const void *a, const void *b) {
    node p1 = *(node*)a, p2 = *(node*)b;
    if(fabs(p1.ang - p2.ang) < eps) return dis(p1, p[1]) > dis(p2, p[1]);
    return p1.ang > p2.ang;
}

int sta[maxn], top = 0;
void Graham(int n) {
    top = 0;
    for(int i = 2; i <= n; i++) 
      if(p[i].y < p[1].y || (p[i].y == p[1].y && p[i].x < p[1].x)) {
        double tmp = p[1].y; p[1].y = p[i].y; p[i].y = tmp;
        tmp = p[1].x; p[1].x = p[i].x; p[i].x = tmp;
    }

    for(int i = 2; i <= n; i++) 
      p[i].ang = atan2(p[i].y - p[1].y, p[i].x - p[1].x);
    qsort(p + 2, n - 1, sizeof(p[0]), cmp);
    sta[++top] = 1;
    for(int i = 2; i <= n; i++) {
        while(top >= 2 && 
            dCmp(cross(minus(p[sta[top]], p[sta[top - 1]]), 
                       minus(p[i], p[sta[top]]))) <= 0) // 严格凸
            top--;
        sta[++top] = i;
    }
}

int main()
{
#ifdef LOCAL
    freopen("in.txt", "r", stdin);
#endif

    int n; scanf("%d", &n);
    for(int i = 1; i <= n; i++) scanf("%lf%lf", &p[i].x, &p[i].y);
    Graham(n);
    // printf("%.6f\n", RoatingCalipers());
    return 0;
}

旋转卡壳求直径

double RoatingCalipers() {
    sta[++top] = 1;  // 先把第一个点补上去
    if(top < 4) return dis(p[sta[1]], p[sta[2]]);

    double mx = 0;
    for(int i = 1, j = 3; i < top; ++i) {
        while(line_dis(p[sta[i]], p[sta[i+1]], p[sta[j]]) <=
            line_dis(p[sta[i]], p[sta[i+1]], p[sta[j % top + 1]]))
            j = j % top + 1;
        mx = max(mx, max(dis(p[sta[i]], p[sta[j]]), 
                    dis(p[sta[i + 1]], p[sta[j]])));
    }
    return mx;
}

计算多边形有向面积

ll cross(ll x1, ll y1, ll x2, ll y2) {return x1 * y2 - x2 * y1;}

ll x_0, y_0, ans = 0;
scanf("%lld%lld", &x_0, &y_0);

ll xx = x_0, yy = y_0;
for(int i = 2; i <= n; i++) {
    ll x, y; scanf("%lld%lld", &x, &y);
    ans += cross(x_0, y_0, x, y);
    x_0 = x, y_0 = y;
}
ans += cross(x_0, y_0, xx, yy);

Others

ASCII 表

ASCII码值也有空格字符？_百度知道

编译 bash 脚本

fileName=$1
mkdir -p target
case $fileName in
    *.c)
        fileNameWithoutExt=`basename $fileName .c`
        gcc -std=c99 -DLOCAL -fsanitize=undefined $fileName -o target/$fileNameWithoutExt
        ;;
    *.cpp)
        fileNameWithoutExt=`basename $fileName .cpp`
        g++ -std=c++17 -DLOCAL -fsanitize=undefined $fileName -o target/$fileNameWithoutExt
        ;;
esac

./target/$fileNameWithoutExt 2> error.log
echo "finish $fileName" >> error.log

优化参数

#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast”)

平面最近点对

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
struct Point{double x,y;}a[2000000],tmp[2000000];
int n,b[2000000];
const double inf=0x7fffffff;
double sqr(double x){return x*x;}
double dis(int l,int r){return sqr(a[l].x-a[r].x)+sqr(a[l].y-a[r].y);}
int cmp(const Point &a,const Point &b){return a.x==b.x?a.y<b.y:a.x<b.x;}
void merge(int l,int r)
{
	int mid=(l+r)>>1,i=l,j=mid+1;
	for(int k=l;k<=r;k++)
	{
		if(i<=mid&&(j>r||a[i].y<a[j].y))tmp[k]=a[i++];
		else tmp[k]=a[j++];
	}
	for(int i=l;i<=r;i++)a[i]=tmp[i];
}
double solve(int l,int r)
{
	if(l>=r)return inf;
	if(l+1==r){if(a[l].y>a[r].y)swap(a[l],a[r]);return dis(l,r);}
	int mid=(l+r)>>1,t=a[mid].x,cnt=0;
	double d=min(solve(l,mid),solve(mid+1,r));
	merge(l,r);
	for(int i=l;i<=r;i++)
		if(sqr(a[i].x-t)<d)
			b[++cnt]=i;
	for(int i=1;i<=cnt;i++)
		for(int j=i+1;j<=cnt&&sqr(a[b[j]].y-a[b[i]].y)<d;j++)
			d=min(d,dis(b[j],b[i]));
	return d;
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)scanf("%lf%lf",&a[i].x,&a[i].y);
	sort(a+1,a+n+1,cmp);
	printf("%.4lf",sqrt(solve(1,n)));
}

莫几

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define eps 1e-9
int sgn(double x){
    if(fabs(x)<eps)return 0;
    if(x<0)return -1;
    return 1;
}
//int sgn(ll x){
//    if(x==0)return 0;
//    if(x<0)return -1;
//    return 1;
//}
const double pi=acos(-1.0);
double cmp(double a,double b){return sgn(a-b);}
double sqr(double x){return x*x;}
struct Point{
    double x,y;
    Point(){}
    Point(double xx,double yy){x=xx;y=yy;}
    void input(){scanf("%lf %lf",&x,&y);}
    void output(){printf("%.0f %.0f\n",x,y);}
    bool operator ==(const Point &p)const{return sgn(x-p.x)==0&&sgn(y-p.y)==0;}
    bool operator !=(const Point &p)const{return sgn(x-p.x)!=0||sgn(y-p.y)!=0;}
    bool operator < (const Point &p)const{
        return sgn(x-p.x)<0||(sgn(x-p.x)==0&&sgn(y-p.y)<0);
    }
    Point operator + (const Point &p)const{
        return {x+p.x,y+p.y};
    }
    Point operator - (const Point &p)const{
        return {x-p.x,y-p.y};
    }
    Point operator * (double k)const{
        return {x*k,y*k};
    }
    Point operator / (const double &k)const{
//assert(k!=0);
        return {x/k,y/k};
    }
    double dot(Point p) const{return p.x*x+p.y*y;}
    double cross(Point p) const {return x * p.y - y * p.x;}
    double dis(Point p) const {return sqrt(sqr(x - p.x) + sqr(y - p.y));}
    double abs() const{return sqrt(sqr(x)+sqr(y));}
    double abs2() const{return sqr(x)+sqr(y);}
    Point rot(Point p,double a){
//逆时针旋转
        Point v = (*this) - p;
        double c = cos(a), s = sin(a);
        return Point(p.x + v.x*c - v.y*s,p.y + v.x*s + v.y*c);
    }
    Point rotLeft() const{return Point(-y,x);}
    Point rotRight() const{return Point(y,-x);}
    double getW() const{return atan2(y,x);}
    Point unit()const{
        if(sgn(abs())==0)return (*this);
        else return {x/abs(),y/abs()};
    }
    Point trunc(double r)const{Point tmp=unit();return tmp*r;}
};
double cross(Point p1,Point p2,Point p3){
    return (p2-p1).cross(p3-p1);
}
double dot(Point p1,Point p2,Point p3){
    return (p2-p1).dot(p3-p1);
}
struct Line{
    Point s,e;//有向直线
    double ang;
    Line(){}
    Line(Point ss,Point ee){s=ss;e=ee;}
    void input(){s.input();e.input();}
    bool operator ==(const Line &v)const{return s==v.s&&e==v.e;}
    double len(){return (e-s).abs();}
    void calcAng(){ang= atan2(dir().y,dir().x);}
    Point dir(){return e-s;}
    int checkLP(Point p){
/* s e p make a counterclockwise 1
* s e p make a clockwise 2
* p is on a line p s e 3
* p is on a line s e p 4
* p is on a seg s e 5
* error 6 */
        int tmp = sgn(cross(s,p,e));
        if(tmp<0)return 1;
        if(tmp>0)return 2;
        int dt=sgn(dot(p,s,e));
        if(dt<=0)return 5;
        if(sgn(dot(s,p,e))>0)return 4;
        if(sgn(dot(s,p,e))<0)return 3;
        assert(0);
    }
    int checkLL(Line v){
// 3 coincide 2 parallel 1 orthogonal 0 others
        int tmp = sgn((e-s).cross(v.e-v.s));
        if(tmp==0){
            if(v.checkLP(e)>2)return 3;
            return 2;
        }
        if(sgn((e-s).dot(v.e-v.s))==0)return 1;
        return 0;
    }
    int checkSS(Line v){
// 2 not strict 1 strict 0 not ins
        if(checkLP(v.s)==5|| checkLP(v.e)==5)return 2;
        if(v.checkLP(s)==5||v.checkLP(e)==5)return 2;
        int tmp=sgn(cross(s,e,v.s)* cross(s,e,v.e));
        int tmp2=sgn(cross(v.s,v.e,s)* cross(v.s,v.e,e));
        if(tmp<0&&tmp2<0)return 1;
        return 0;
    }
    int checkLS(Line v){//untested 2严格1不严格
        int d1 = sgn((e-s).cross(v.s-s));
        int d2 = sgn((e-s).cross(v.e-s));
        if((d1^d2)==-2) return 2;
        return (d1==0||d2==0);
    }
    Point getLL(Line v){
        double tmp=(s-v.s).cross(v.e-v.s),tmp2=(v.e-v.s).cross(e-v.s);
        return (s*tmp2+e*tmp)/(tmp+tmp2);
    }
    Point proj(Point p){
        return s+(e-s).trunc(dot(s,p,e)/len());
    }
    double disLP(Point p){return p.dis(proj(p));}
    double disSP(Point p){
        if(checkLP(proj(p))!=5)return min(p.dis(s),p.dis(e));
        return disLP(p);
    }
};
bool onSeg(Point p,Point a,Point b){return Line(a,b).checkLP(p)==5;}
struct Circle{
    Point p;
    double r;
    Circle(){}
    Circle(Point pp,double rr){p=pp;r=rr;}
    bool operator == (const Circle &c)const{
        return (p==c.p)&&(sgn(r-c.r)==0);
    }
    Point point(double a){return p+Point(r*cos(a),r*sin(a));}
    void input(){p.input();scanf("%lf",&r);}
    int include(Point q){if(sgn(p.dis(q)-r)==0)return 1;if(sgn(p.dis(q)-r)<0)return 2;return 0;}
    int checkCC(Circle c){
//0 内含 1 内切 2 相交 3 外切 4 相离
        double d=c.p.dis(p);
        if(sgn(d-r-c.r)>0)return 4;
        if(sgn(d-r-c.r)==0)return 3;
        if(sgn(d- fabs(r-c.r))==0)return 1;
        if(sgn(d- fabs(r-c.r))<0)return 0;
        return 2;
    }
    int checkCL(Line l){
//2 相交 1相切 0 相离
        if(sgn(l.disLP(p)-r)==0)return 1;
        if(sgn(l.disLP(p)-r)<0)return 2;
        return 0;
    }
    vector<Point> getCL(Line v){
//相切给出两个
        if(checkCL(v)==0)return {};
        vector<Point> tmp;
        double d=v.disLP(p);
        double x=sqrt(r*r-d*d);
        if(sgn(d-r)==0){
            tmp.pb(v.proj(p));
            tmp.pb(v.proj(p));
        }else{
            tmp.pb(v.proj(p)-(v.e-v.s).trunc(x));
            tmp.pb(v.proj(p)+(v.e-v.s).trunc(x));
//和v方向一致
        }
        return tmp;
    }
    double circ(){return 2*pi*r;}
    double area(){return pi*r*r;}
    vector<Point> getCC(Circle c){//沿当前逆时针给出,相切给出两个
        if(checkCC(c)==0|| checkCC(c)==4)return {};
        double b=p.dis(c.p),cosA=(r*r+b*b-c.r*c.r)/(2*r*b);
        double tmp=r*cosA,h=sqrt(r*r-tmp*tmp);
        Point v=(c.p-p).trunc(tmp).rotLeft().trunc(h);
        Point ini=p+(c.p-p).trunc(tmp);
        return {ini-v,ini+v};
    }
};
double polyArea(const vector<Point> &p){
    double ans=0;
    int sz=p.size();
    for(int i=0;i<sz;i++){
        ans+=(p[i].cross(p[(i+1)%sz]));
    }
    return fabs(ans)/2.0;
}
double polyCir(const vector<Point> &p){
    double ans=0;
    int sz=p.size();
    for(int i=0;i<sz;i++){
        ans+=(p[i].dis(p[(i+1)%sz]));
    }
    return ans;
}
bool isConvex(const vector<Point> &p,int flag=0){//0 严格 1 非严格 counterclockwise
    int sz=p.size();
    for(int i=0;i<sz;i++){
        int x=Line(p[i],p[(i+1)%sz]).checkLP(p[(i+2)%sz]);
        if(x!=1){
            if(flag){if(x==2)return false;}
            else return false;
        }
    }
    return true;
}
int contain(vector<Point> ps, Point p){ //2:inside 1:onSeg 0:outside
    int n = ps.size(), ret = 0;
    for(int i=0;i<n;i++){
        Point u=ps[i],v=ps[(i+1)%n];
        if(onSeg(p,u,v)) return 1;
        if(cmp(u.y,v.y)<=0) swap(u,v);
        if(cmp(p.y,u.y) >0 || cmp(p.y,v.y) <= 0) continue;
        ret ^= sgn(cross(p,u,v)) > 0;
    }
    return ret*2;
}
double convexDiameter(vector<Point> ps){
    int n = ps.size(); if(n <= 1) return 0;
    int is = 0, js = 0;
    for(int k=0;k<n;k++)is=ps[k]<ps[is]?k:is, js = ps[js] < ps[k]?k:js;
    int i = is, j = js;
    double ret = ps[i].dis(ps[j]);
    do{
        if((ps[(i+1)%n]-ps[i]).cross(ps[(j+1)%n]-ps[j]) >= 0)
            (++j)%=n;
        else
            (++i)%=n;
        ret = max(ret,ps[i].dis(ps[j]));
    }while(i!=is || j!=js);
    return ret;
}
vector<Point> convexHull(vector<Point>A, int flag = 1) { // flag=0 不严格 flag=1 严格
    int n = A.size(); vector<Point>ans(n * 2);
    if(n==1)return A;
    sort(A.begin(), A.end()); int now = -1;
    for (int i = 0; i < A.size(); i++) {
        while (now > 0 && sgn(cross(ans[now-1],ans[now],A[i]))<flag)now--;
        ans[++now] = A[i];
    } int pre = now;
    for (int i = n - 2; i >= 0; i--) {
        while (now > pre && sgn(cross(ans[now-1],ans[now],A[i]))<flag)now--;
        ans[++now] = A[i];
    } ans.resize(now); return ans;
}
vector<Point> norm(vector<Point> p,Point q){//极角排序
    sort(p.begin(),p.end(),[&](Point a,Point b){
        int d = sgn((a-q).cross(b-q));
        if(d == 0){
            return sgn(a.dis(q)-b.dis(q)) < 0;
        }
        return d > 0;
    });
    return p;
}
vector<Point> (vector<Point> ps){
    auto mi=ps[0];graHam
    for(auto i:ps)mi=min(mi,i);
    ps = norm(ps,mi);
    int n=ps.size();
    vector<Point> ans(n*2);
    int top = 0;
    if(n == 1){
        top = 1;
        ans[0] = ps[0];
    }else if(n == 2){
        top = 2;
        ans[0] = ps[0];
        ans[1] = ps[1];
        if(ans[0] == ans[1])top--;
    }else{
        ans[0] = ps[0];
        ans[1] = ps[1];
        top = 2;
        for (int i = 2; i < n; i++) {
            while (top > 1 &&
                    sgn((ans[top-1]-ans[top - 2]).cross(ps[i]-ans[top-2]))<=0)
                top--;
            ans[top++] = ps[i];
        }
        if (top== 2 && (ans[0] == ans[1]))top--;
    }
    ans.resize(top);return ans;
}
int main(){
}