ACM模板-稳赚个人版(持续更新)

啊我真的不会加注释

头文件

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
#include<iostream>
#include<map>
#include<set>
#include<queue>
#include<stack>
#include<string>
#include<vector>
#include<sstream>
#include<utility>
#include<algorithm>
#define pf printf
#define INF 0x3f3f3f3f
#define sc(x) scanf("%d", &x)
#define scs(x) scanf("%s", x)
#define scd(x) scanf("%lf", &x)
#define scl(x) scanf("%lld", &x)
#define mst(a,x) memset(a, x, sizeof(a))
#define rep(i,s,e) for(int i = s; i < e; i++)
#define dep(i,e,s) for(int i = e; i >= s; i--)
using namespace std;
const int seed = 131;
const int maxn = 1e5 + 5;
const int mod = 1e9 + 7;
const double eps = 1e-10;
const double PI = acos(-1.0);
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> VI;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

字符串操作

char函数
1
2
3
4
5
6
7
8
9
10
11
12
char s1[maxn], s2[maxn];
char c;
int n;
strcat(s1, s2); // s1 += s2;
strncat(s1, s2, n); // 加上s2的前n个字符
strchr(s1, c); // 返回s1中第一次出现c的位置
strrchr(s1, c); // 返回s1中最后一次出现c的位置
strstr(s1, s2); // 返回s1中第一次出现s2的位置
strcmp(s1, s2); // 比较 能比大小的
strncmp(s1, s2, n); // 比前n个
strcpy(s1, s2); // s1 = s2;
strncpy(s1, s2, n); // s1为s2前n个字符
string函数
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
string s1,s2;
int pos,len;
char c;
s1.find(s2);
// 返回值为s2第一次出现在s1的位置
// 若s2不是s1子串返回 string::npos
s1.replace(pos,len,s2);
// s1从pos位开始长度len的子串替换成s2
s1.substr(pos,len);
s1.insert(pos,s2);
s1.insert(pos,s2,len);
// 插入s2的前len个字符
s1.insert(pos,len,c);
// 插入len个c
s1.erase(pos,len);
字典树
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
// 数组版
int trie[maxn][2];
int cnt[maxn];
int n;
void create(char s[]) {
int u = 0;
int len = strlen(s);
rep (i, 0, len) {
int tmp = s[i] - 'a';
if (!trie[u][tmp]) {
trie[u][tmp] = ++n;
cnt[n]++;
}
else cnt[trie[u][tmp]]++;
u = trie[u][tmp];
}
}
int find(char s[]) {
int u = 0;
int len = strlen(s);
rep (i, 0, len) {
int tmp = s[i] - 'a';
if (!trie[u][tmp]) return 0;
u = trie[u][tmp];
}
return cnt[u];
}


// 指针版
suct trie {
int cnt;
trie* next[26];
trie() {
cnt = 0;
rep (i, 0, 26) next[i] = NULL;
}
};
trie *root, *p;
void insert(char* s) {
p = root;
int len = strlen(s);
rep (i, 0, len) {
int tmp = s[i] - 'a';
if (p->next[tmp] == NULL)
p->next[tmp] = new trie();
p = p->next[tmp];
p->cnt++;
}
}
int find(char* s) {
p = root;
int len = strlen(s);
rep (i, 0, len) {
int tmp = s[i] - 'a';
if (p->next[tmp] == NULL)
return 0;
p = p->next[tmp];
}
return p->cnt;
}
KMP
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
int nex[maxn];
void getnext(char s[]) {
nex[0] = -1;
int i = 0, j = -1;
int len = strlen(s);
while (i < len) {
if (j == -1 || s[i] == s[j]) {
i++; j++;
nex[i] = j;
}
else j = nex[j];
}
}
int kmp(char s1[], char s2[]) {
int i = 0, j = 0;
int len1 = strlen(s1), len2 = strlen(s2);
getnext(s2);
while (i < len1 && j < len2) {
if (j == -1 || s1[i] == s2[j]) {
i++; j++;
}
else j = nex[j];
if (j == len2) return i - j + 1;
}
return 0;
}
/* 关于next数组应用如
if(nex[pos] && pos % (pos - nex[pos]) == 0)
即有s的前pos位有(pos / (pos - nex[pos]))个长度为nex[pos]的前缀*/
//求总前缀数 dp
for (int i = 1;i <= s.length();i++) {
int tmp = nex[i];
while (tmp) {
sum = (sum + 1) % 10007;
tmp = nex[tmp];
}
}
EXKMP
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
int nex[maxn], extend[maxn];
void getnext(char s[]) {
int aa = 0;
int len = strlen(s);
nex[0] = len;
while (aa < len - 1 && s[aa] == s[aa + 1]) aa++;
nex[1] = aa;
aa = 1;
rep (i, 2, len) {
int p = aa + nex[aa] - 1;
int l = nex[i - aa];
if (k + l - 1 >= p) {
int j = (p - i + 1) > 0 ? p - i + 1 : 0;
while (i + j < len&&s[i + j] == s[j]) j++;
nex[i] = j;
aa = i;
}
else nex[i] = l;
}
}
void getextend(char* s1, char* s2) {
int aa = 0;
memset(nex, 0, sizeof(nex));
getnext(s2);
int len1 = strlen(s1), len2 = strlen(s2);
int minl = min(len1, len2);
while (aa < minl && s1[aa] == s2[aa]) aa++;
extend[0] = aa;
aa = 0;
rep (i, 1, len1) {
int p = aa + extend[aa] - 1, l = nex[i - aa];
if (i + l - 1 >= p) {
int j = (p - i + 1) > 0 ? p - i + 1 : 0;
while (i + j < len1&&j < len2&&s1[i + j] == s2[j]) j++;
extend[i] = j;
aa = i;
}
else extend[i] = l;
}
}
manacher
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
int che[2 * maxn];
char s[maxn], ma[2 * maxn];
void manacher(char* s, int len0) {
int len = 0;
ma[len++] = '$';
ma[len++] = '#';
rep (i, 0, len0) {
ma[len++] = s[i];
ma[len++] = '#';
}
ma[len] = 0;
int maxx = 0, num = 0;
rep (i, 0, len) {
che[i] = maxx > i ? min(che[2 * num - i], maxx - i) : 1;
while (ma[i + che[i]] == ma[i - che[i]]) che[i]++;
if (i + che[i] > maxx) {
maxx = i + che[i];
num = i;
}
}
}
int count(int x) {
int ans = -1;
x = x * 2 + 2;
rep(i, 0, x) ans = max(ans, che[i] - 1);
return ans;
}
AC自动机
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
// 计每个单词有无出现 注释里写记单词数的 以*开头
int ans;
struct node {
node* next[26]; // 最大100够的 所有题
node* fail;
int end; // 在单词末尾做标记
//* int id;
node() {
end = 0; //* id = 0;
fail = 0;
mst (next, 0);
}
};
node* root;
// 建字典树
//* int tot;
void insert(char* s) {
node* p = root;
int len = strlen(s);
rep (i, 0, len) {
int tmp = s[i] - 'a';
if (p->next[tmp] == NULL)
p->next[tmp] = new node();
p = p->next[tmp];
}
p->end++;
//* p->id=++tot;
}
queue<node*>q;
// fail数组:root指向NULL 没出现过的指向root 出现过的指向前一个
void getfail() {
root->fail = NULL;
q.push(root);
while (!q.empty()) {
node* fr = q.front();
q.pop();
rep (i, 0, 26)
if (fr->next[i]) {
node* tem = fr->fail;
while (tem) {
if (tem->next[i]) {
fr->next[i]->fail = tem->next[i];
break;
}
tem = tem->fail;
}
if (tem == NULL)
fr->next[i]->fail = root;
q.push(fr->next[i]);
}
}
}
//* num[maxn], mark[maxn], cnt;
void ac_auto(char* s) {
node* p = root;
int len = strlen(s);
rep (i, 0, len) {
int tmp = s[i] - 'a';
while (!p->next[tmp] && p != root) p = p->fail;
p = p->next[tmp];
if (!p) p = root;
node* tem = p;
while (tem != root) {
if (tem->end >= 0)0 {
ans += tem->end;
tem->end = -1; // 出现过了第二次遇到不再统计
}
else break;
/* if(tem->id){
*if(!mark[tem->id])
*num[cnt++] = tem->id;
// num按在s串中出现顺序存id
*mark[tem->id]++;
//mark存出现与否 顺便存次数
}*/
tem = tem->fail;
}
}
}
后缀数组
1
2


最大最小表示法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
int getmin(char *s) {
int len = strlen(s);
int i = 0, j = 1, k = 0;
while (i < len && j < len && k < len) {
int tmp = s[(i + k) % len] - s[(j + k) % len];
if (!tmp) k++;
else {
if (tmp > 0) i += k + 1;
else j += k + 1;
if (i == j) j++;
k = 0;
}
}
return min(i, j);
}
int getmax(char *s) {
int len = strlen(s);
int i = 0, j = 1, k = 0;
while (i < len && j < len && k < len) {
int tmp = s[(i + k) % len] - s[(j + k) % len];
if (!tmp) k++;
else {
if (tmp < 0) i += k + 1;
else j += k + 1;
if (i == j) j++;
k = 0;
}
}
return min(i, j);
}

自闭图论

最短路dijkstra
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
int vis[maxn];
int dis[maxn];
int mp[maxn][maxn];
void init() {
rep (i, 0, maxn)
rep (j, 0, maxn)
mp[i][j] = INF;
}
void dij(int s) {
int i, j;
rep (i, 0, n) vis[i] = 0, dis[i] = INF;
dis[s] = 0;
while (1) {
j = -1;
rep (i, 0, n)
if (!vis[i] && (j == -1 || dis[i] < dis[j])) j = i;
if (j == -1) break;
vis[j] = 1;
rep (i, 0, n)
dis[i] = min(dis[i], dis[j] + mp[j][i]);
}
}
稳定婚姻问题
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
int b[maxn][maxn], g[maxn][maxn];
// b 每个男生按好感位次排下来的女生
// g 每个女生对应每个男生的好感度
int bm[maxn], gm[maxn];
// 对应异性号数
int vis[maxn][maxn];
void stable_marriage() {
mst (bm, -1);
mst (gm, -1);
mst (vis, 0);
queue<int> q;
rep (i, 1, n + 1) q.push(i);
int fr, nex;
while (!q.empty()) {
fr = q.front();
q.pop();
rep (i, 1, n + 1) {
nex = b[fr][i];
if (vis[fr][nex]) continue;
vis[fr][nex] = 1;
if (gm[nex] == -1) {
gm[nex] = fr;
bm[fr] = nex;
break;
}
else if (g[nex][gm[nex]] > g[nex][fr]) {
q.push(gm[nex]);
gm[nex] = fr;
bm[fr] = nex;
break;
}
}
}
}
二分匹配匈牙利算法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
int ans;
int mp[maxn][maxn];
int vis[maxn], line[maxn];
void init() {
ans = 0;
mst (mp, 0);
mst (line, 0);
}
int dfs(int x) {
rep (i, 1, n + 1)
if (!vis[i] && mp[i][x]) {
vis[i] = 1;
if (!line[i] || dfs(line[i])) {
line[i] = x;
return 1;
}
}
return 0;
}
void solve() {
rep (i, 1, n + 1){
mst (vis, 0);
if (dfs(i)) ans++;
}
}
强连通tarjan
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
int cnt, id;
int dfn[maxn], low[maxn];
int ins[maxn];
int scc[maxn];
stack<int>s;
vector<int>vv[maxn];
void init() {
cnt = id = 0;
mst (dfn, 0);
mst (low, 0);
mst (ins, 0);
mst (scc, 0);
rep (i, 1, n + 1) vv[i].clear();
}
void tarjan(int x) {
dfn[x] = low[x] = ++id;
ins[x] = 1;
s.push(x);
int tmp;
rep (i, 0, vv[x].size()) {
tmp = vv[x][i];
if (!dfn[tmp]) {
tarjan(tmp);
low[x] = min(low[x], low[tmp]);
}
else if(ins[tmp]) low[x] = min(low[x], dfn[tmp]);
}
if (low[x] == dfn[x]) {
cnt++;
do {
tmp = s.top();
s.pop();
ins[tmp] = 0;
scc[tmp] = cnt;
} while (x != tmp);
}
}
void solve() {
rep (i, 1, n + 1)
if (!dfn[i])
tarjan(i);
mst (ins, 0); // 入度
mst (out, 0); // 出度
rep (i, 1, n + 1)
rep (j, 0, vv[i].size())
if (scc[i] != scc[vv[i][j]]) {
ins[scc[vv[i][j]]]++;
out[scc[i]]++;
}
}
双连通tarjan
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
//还没整理
int m, n, k, t;
int a, b, c[maxn], d;
int cnt, id, sum, ans;
int dfn[maxn], low[maxn];
int ins[maxn];
stack<int>s;
vector<int>vv[maxn];
void tarjan(int x, int y) {
dfn[x] = low[x] = ++id;
ins[x] = 1;
s.push(x);
int flag = 1;
for (int i = 0; i < vv[x].size(); i++) {
int tmp = vv[x][i];
if (tmp == y && flag) {
flag = 0;
continue;
}
if (!ins[tmp]) {
tarjan(tmp, x);
low[x] = min(low[x], low[tmp]);
if (low[tmp] > dfn[x]) {
int u, tt = 0;
do {
u = s.top();
s.pop();
tt += c[u];
} while (u != tmp);
ans = min(ans, abs(sum - tt * 2));
c[x] += tt;
cnt++;
}
}
else low[x] = min(low[x], dfn[tmp]);
}
}
int main() {
while (~scanf("%d%d", &n, &m)) {
sum = id = cnt = 0;
ans = INF;
memset(ins, 0, sizeof(ins));
memset(dfn, 0, sizeof(dfn));
for (int i = 0; i < n; i++) {
scanf("%d", &c[i]);
sum += c[i];
vv[i].clear();
}
for (int i = 0; i < m; i++) {
scanf("%d%d", &a, &b);
vv[a].push_back(b);
vv[b].push_back(a);
}
tarjan(0, 0);
if (cnt) printf("%d\n", ans);
else printf("impossible\n");
}
}

数据结构

并查集
1
2
3
4
5
6
7
8
9
int find(int x) {
if (vis[x] == x) return x;
else return vis[x] = find(vis[x]);
}
void change(int x, int y) {
c = find(x);
d = find(y);
if (c != d) vis[c] = d;
}
树状数组
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
int tree[maxn];
int lowbit(int i) {
return i & (-i);
}
void updata(int i, int x) {
for (; i <= n; i += lowbit(i))
tree[i] += x;
}
int sum(int n) {
int ans = 0;
for (int i = n; i > 0; i -= lowbit(i))
ans += tree[i];
return ans;
}

// 二维
void updata(int i, int j, int x) {
while (i <= 1001) {
int aa = j;
while (aa <= 1001) {
tree[i][aa] += x;
aa += lowbit(aa);
}
i += lowbit(i);
}
}
int sum(int x, int y) {
int ans = 0;
while (x) {
int tmp = y;
while (tmp) {
ans += tree[x][tmp];
tmp -= lowbit(tmp);
}
x -= lowbit(x);
}
return ans;
}

数学

快速幂
1
2
3
4
5
6
7
8
9
10
ll quickpow(int a, int b) {
ll ans = 1;
ll n1 = a;
while (b) {
if (b & 1) ans = (ans * n1) % mod;
b >>= 1;
n1 = (n1*n1) % mod;
}
return ans;
}
矩阵快速幂
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
struct matrix {
int m[maxn][maxn];
}ans, res, tmp;
matrix mul(matrix a, matrix b) {
rep (i, 1, maxn + 1)
rep (j, 1, maxn + 1)
tmp.m[i][j] = 0;
rep (i, 1, maxn + 1)
rep (j, 1, maxn + 1)
rep (k, 1, maxn + 1)
tmp.m[i][j] = (tmp.m[i][j] + a.m[i][k] * b.m[k][j]) % mod;
return tmp;
}
void quickpower(int n) {
rep (i, 1, maxn + 1)
rep (j, 1, maxn + 1)
if (i == j) ans.m[i][j] = 1;
else ans.m[i][j] = 0;
while (n) {
if (n & 1) ans = mul(ans, res);
res = mul(res, res);
n = n >> 1;
}
}
高精度
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// 想不到吧是Java
import java.math.*;
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
while(sc.hasNext()){
// 常见函数
BigInteger.valueOf(); // 大数互转,int转大数,string转大数
BigInteger array[]=new BigInteger[maxn];
add(); subtract(); multiply(); divide();
compareTo(); mod(); pow(); gcd();
System.out.println(a.stripTrailingZeros().toPlainString()); // 实数的输出去除末尾0
Arrays.sort(a,0,n); // 数组排序
}
}
}
中国剩余定理
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
// crt 我恨
ll a[maxn], r[maxn];
ll exgcd (ll a, ll b, ll &x, ll &y){
if (!b) {
x=1, y=0;
return a;
}
else {
ll ans = exgcd(b, a%b, y, x);
y -= (a/b)*x;
return ans;
}
}
void excrt() {
ll m1, r1, m2, r2;
ll x, y, t;
ll c, d;
m1 = a[0], r1 = r[0];
rep (i, 1, tot){
m2 = a[i], r2 = r[i];
c = r2 - r1;
d = exgcd(m1, m2, x, y);
t = m2 / d;
x *= c / d;
x = (x % t + t) % t;
r1 = x * m1 + r1;
m1 = m1 * m2 / d;
r1 = (r1 % m1 + m1) % m1;
}
}
打表素数及莫比乌斯函数
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
int p[maxn], u[maxn], vis[maxn];
int pn;
void make_table() {
mst (vis, 0);
u[1] = 1;
pn = 0;
rep (i, 2, maxn) {
if (!vis[i]) {
p[pn++] = i;
u[i] = -1;
}
for (int j = 0; j < pn && i*p[j] < maxn; j++) {
vis[i*p[j]] = 1;
if (i%p[j]) u[i*p[j]] = -u[i];
else {
u[i*p[j]] = 0;
break;
}
}
}
}
博弈
1
2
3
4
5
6
7
/* 巴什博弈:一堆物品n两人轮流取物,一次最多m
根据n % (m + 1)是否为零判断胜者
威佐夫博奕:两堆物品a, b两人轮流取物,一次只能在一堆任意取或是两堆取同样多 //默认a < b
根据(int)((double)(1.0 + sqrt(5.0)) / 2.0) * (b - a))是否等于a判断胜者
Fibonacci博弈:一堆物品n,两人轮流取物,每一次能取的个数是上一次的两倍以内,最后取完胜
n为Fibonacci数时先手败 */
// 以下sg函数 打表 dfs

计算几何

二维几何
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
struct point {
double x, y;
point(double a = 0, double b = 0) {
x = a, y = b;
}
}; // 点
struct line {
point s, e;
line(point a, point b) {
s = a, e = b;
}
line() {
}
}; // 线
double getdis(point a, point b) {
double xx = a.x - b.x, yy = a.y - b.y;
return sqrt(xx * xx + yy * yy);
} // 两点距离
double multi(point a, point b, point c) {
double xa, ya, xb, yb;
xa = b.x - a.x;
ya = b.y - a.y;
xb = c.x - b.x;
yb = c.y - b.y;
return xa * xb + ya * yb;
} // 点乘
double multi(point a, point b, point c) {
double xa, ya, xb, yb;
xa = b.x - a.x;
ya = b.y - a.y;
xb = c.x - b.x;
yb = c.y - b.y;
return xa * yb - xb * ya;
} // 叉乘
int judge(line a, line b) {
if (max(a.s.x, a.e.x) >= min(b.s.x, b.e.x) &&
max(a.s.y, a.e.y) >= min(b.s.y, b.e.y) &&
max(b.s.x, b.e.x) >= min(a.s.x, a.e.x) &&
max(b.s.y, b.e.y) >= min(a.s.y, a.e.y) &&
multi(a.s, b.s, b.e)*multi(a.e, b.s, b.e) <= 0 &&
multi(b.s, a.s, a.e)*multi(b.e, a.s, a.e) <= 0
) return 1;
else return 0;
} // 判断线段是否相交
point p[maxn];
double area(){
double ans = 0, tmp;
p[n].x = p[0].x, p[n].y = p[0].y;
rep (i, 0, n) {
tmp = p[i].x * p[i + 1].y - p[i + 1].x * p[i].y;
ans += tmp;
}
return ans;
} // 多边形面积
double gx, gy;
point p[maxn];
void find_gra(){
double area = 0, tmp;
rep (i, 1, n - 1) {
tmp = (p[i].x - p[0].x) * (p[i+1].y - p[0].y) - (p[i+1].x - p[0].x) * (p[i].y - p[0].y);
area += tmp;
gx += (p[0].x + p[i].x + p[i + 1].x)*tmp;
gy += (p[0].y + p[i].y + p[i + 1].y)*tmp;
}
gx = gx / 3 / area, gy = gy / 3 / area;
} // 求重心坐标

// 以下凸包Graham
int top;
point p[maxn], s[maxn];
int iszero(double x) {
return fabs(x) < eps;
}
int cmp(point a, point b) {
double tt = multi(a, b, p[0]);
if (tt > 0 || iszero(tt) && getdis(a, p[0]) < getdis(b, p[0]))
return 1;
return 0;
}
void graham() {
point tmp;
rep (i, 1, n)
if (p[i].y < p[0].y || (p[i].y == p[0].y&&p[i].x < p[0].x)) {
tmp = p[i];
p[i] = p[0];
p[0] = tmp;
}
sort(p + 1, p + n, cmp);
s[0] = p[0];
s[1] = p[1];
s[2] = p[2];
top = 2;
rep (i, 3, n) {
while (top >= 2 && multi(s[top - 1], s[top], p[i]) <= eps)
top--;
s[++top] = p[i];
}
}

其他

1
2
vv.erase(lower_bound(vv.begin(), vv.end(), a));
// vector删点 在vv删掉a