PS
내가 쓰는 코드 스니펫
woojin042
2025. 3. 29. 01:55
{
"CT" : {
"prefix": "ct",
"body": [
"#include<bits/stdc++.h>",
"using namespace std;",
"",
"int main(){",
" ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);",
" return 0;",
"}"
],
},
"CP": {
"prefix": "cp",
"body": [
"#include<bits/stdc++.h>",
"#include <ext/pb_ds/assoc_container.hpp>",
"#include <ext/pb_ds/tree_policy.hpp>",
"using namespace std;",
"using namespace __gnu_pbds;",
"template<typename T>",
"using ordered_set = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;",
"template<typename T>",
"using ordered_multiset = tree<T, null_type, less_equal<T>, rb_tree_tag,tree_order_statistics_node_update>;",
"template<typename T>",
"void m_erase(ordered_set<T> &OS, int val){",
" int index = OS.order_of_key(val);",
" auto it = OS.find_by_order(index);",
" if(*it == val) OS.erase(it);",
"}",
"",
"#define all(v) v.begin(),v.end()",
"#define mset(a, b) memset(a, b, sizeof(a))",
"#define sz(a) a.size()",
"#define X first",
"#define Y second",
"#define forr(i, n) for(int i = 0; i < (n); i++)",
"#define fors(i, s, e) for(int i = (s); i <= (e); i++)",
"#define fore(i, e, s) for(int i = (e); i >= (s); i--)",
"#define endl '\\n'",
"#define int long long",
"",
"using ll = long long;",
"using pi = pair<int, int>;",
"using vi = vector<int>;",
"using vvi = vector<vi>;",
"using vpi = vector<pi>;",
"using tp = tuple<int, int, int>;",
"using vtp = vector<tp>;",
"using cpx = complex<double>;",
"using vcp = vector<cpx>;",
"",
"const int dy[]={0, 1, 0, -1};",
"const int dx[]={1, 0, -1, 0};",
"const int inf=1e18, mod=1e9+7;",
"const double PI = acos(-1);",
"const int N=100'010;",
"",
"",
"void solve(){",
"",
"}",
"",
"signed main(){",
" ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);",
" int t;cin>>t;while(t--)solve();",
" return 0;",
"}"
]
},
"OJ": {
"prefix": "oj",
"body": [
"#include<bits/stdc++.h>",
"#include <ext/pb_ds/assoc_container.hpp>",
"#include <ext/pb_ds/tree_policy.hpp>",
"using namespace std;",
"using namespace __gnu_pbds;",
"template<typename T>",
"using ordered_set = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;",
"template<typename T>",
"using ordered_multiset = tree<T, null_type, less_equal<T>, rb_tree_tag,tree_order_statistics_node_update>;",
"template<typename T>",
"void m_erase(ordered_set<T> &OS, int val){",
" int index = OS.order_of_key(val);",
" auto it = OS.find_by_order(index);",
" if(*it == val) OS.erase(it);",
"}",
"",
"#define all(v) v.begin(),v.end()",
"#define mset(a, b) memset(a, b, sizeof(a))",
"#define sz(a) a.size()",
"#define X first",
"#define Y second",
"#define forr(i, n) for(int i = 0; i < (n); i++)",
"#define fors(i, s, e) for(int i = (s); i <= (e); i++)",
"#define fore(i, e, s) for(int i = (e); i >= (s); i--)",
"#define endl '\\n'",
"#define int long long",
"",
"using ll = long long;",
"using pi = pair<int, int>;",
"using vi = vector<int>;",
"using vvi = vector<vi>;",
"using vpi = vector<pi>;",
"using tp = tuple<int, int, int>;",
"using vtp = vector<tp>;",
"using cpx = complex<double>;",
"using vcp = vector<cpx>;",
"",
"const int dy[]={0, 1, 0, -1};",
"const int dx[]={1, 0, -1, 0};",
"const int inf=1e18, mod=1e9+7;",
"const double PI = acos(-1);",
"const int N=100'010;",
"",
"",
"void solve(){",
"",
"}",
"",
"signed main(){",
" ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);",
" solve();",
" return 0;",
"}"
]
},
"sumtree": {
"prefix": "sumtree",
"body": [
"struct Seg{",
" static const int sz=1<<20;",
" int tree[sz<<1];",
"",
" void init(){",
" for(int i=sz-1; i; i--) tree[i]=tree[i*2]+tree[i*2+1];",
" }",
"",
" void update(int r, int v){",
" r+=sz;",
" tree[r]=v;",
" while(r>1){",
" r/=2;",
" tree[r]=tree[r*2]+tree[r*2+1];",
" }",
" }",
"",
" int sum(int l, int r, int idx=1, int s=0, int e=sz-1){",
" if(l<=s && e<=r) return tree[idx];",
" if(e<l || r<s) return 0;",
" int mid=s+e>>1;",
" return sum(l, r, idx*2, s, mid)+sum(l, r, idx*2+1, mid+1, e);",
" }",
"",
" int& operator[](int idx){",
" return tree[sz+idx];",
" }",
"} seg;"
]
},
"maxtree": {
"prefix": "maxtree",
"body": [
"struct Seg{",
" static const int sz=1<<20;",
" int tree[sz<<1];",
"",
" void init(){",
" for(int i=sz-1; i; i--) tree[i]=max(tree[i*2], tree[i*2+1]);",
" }",
"",
" void update(int r, int v){",
" r+=sz;",
" tree[r]=v;",
" while(r>1){",
" r/=2;",
" tree[r]=max(tree[r*2], tree[r*2+1]);",
" }",
" }",
"",
" int query(int l, int r, int idx=1, int s=0, int e=sz-1){",
" if(l<=s && e<=r) return tree[idx];",
" if(e<l || r<s) return -inf;",
" int mid=s+e>>1;",
" return max(query(l, r, idx*2, s, mid), query(l, r, idx*2+1, mid+1, e));",
" }",
"",
" int& operator[](int idx){",
" return tree[sz+idx];",
" }",
"} seg;"
]
},
"mintree": {
"prefix": "mintree",
"body": [
"struct Seg{",
" static const int sz=1<<20;",
" int tree[sz<<1];",
" ",
" void init(){",
" for(int i=sz-1; i; i--) tree[i]=min(tree[i*2], tree[i*2+1]);",
" }",
" ",
" void update(int r, int v){",
" r+=sz;",
" tree[r]=v;",
" while(r>1){",
" r/=2;",
" tree[r]=min(tree[r*2], tree[r*2+1]);",
" }",
" }",
" ",
" int query(int l, int r, int idx=1, int s=0, int e=sz-1){",
" if(l<=s && e<=r) return tree[idx];",
" if(e<l || r<s) return inf;",
" int mid=s+e>>1;",
" return min(query(l, r, idx*2, s, mid), query(l, r, idx*2+1, mid+1, e));",
" }",
" int& operator[](int idx){",
" return tree[sz+idx];",
" }",
"} seg;"
]
},
"ccw": {
"prefix": "ccw",
"body": [
"int ccw(const pi& a, const pi& b, const pi& c){",
" int cross=(b-a)/(c-a);",
" if(cross==0) return 0;",
" return (cross>0) ? 1:-1;",
"}"
],
},
"convex hull": {
"prefix": "convexhull",
"body": [
"vpi graham(vpi& p){",
" int sz=p.size();",
" swap(p[0], *min_element(all(p)));",
" sort(p.begin()+1, p.end(), [&](const pi& a, const pi& b){",
" int r=ccw(p[0], a, b);",
" return r>0 || r==0 && a<b;",
" });",
"",
" int cc=0;",
" vpi ret;",
" for(int i=0; i<sz; i++){",
" while(cc>1 && ccw(ret[cc-2], ret[cc-1], p[i])<=0){",
" cc--;",
" ret.pop_back();",
" }",
" cc++;",
" ret.push_back(p[i]);",
" }",
" return ret;",
"}"
]
},
"strongly connected component": {
"prefix": "scc",
"body": [
"const int MAX=100'010;",
"stack<int> st;",
"int sn[MAX], dfsn[MAX], cnt, sccn;",
"vi adj[MAX];",
"bool finished[MAX];",
"",
"int dfs(int cur){",
" int ret=dfsn[cur]=++cnt;",
" st.push(cur);",
"",
" for(int nxt:adj[cur]){",
" if(dfsn[nxt]==0) ret=min(ret, dfs(nxt));",
" else if(!finished[nxt]) ret=min(ret, dfsn[nxt]);",
" }",
"",
" if(ret==dfsn[cur]){",
" while(1){",
" int t=st.top(); st.pop();",
" sn[t]=sccn;",
" finished[t]=1;",
" if(t==cur) break;",
" }",
" sccn++;",
" }",
"",
" return ret;",
"}"
]
},
"union find" : {
"prefix": "unionfind",
"body": [
"struct UnionFind{",
" static const int MAX=100'010;",
" int p[MAX];",
"",
" UnionFind(){ mset(p, -1); }",
"",
" void init(){",
" mset(p, -1);",
" }",
" ",
" int find(int cur){",
" if(p[cur]<0) return cur;",
" return p[cur]=find(p[cur]);",
" }",
" ",
" void merge(int a, int b){",
" a=find(a); b=find(b);",
" if(a==b) return;",
" p[a] += p[b];",
" p[b] = a;",
" }",
"} uf;",
]
},
"trie" : {
"prefix": "trie",
"body": [
"struct node{",
" int nxt[26];",
" char val;",
" node() { mset(nxt, -1); val='a'; }",
" node(char c) : val(c) { mset(nxt, -1); }",
"};",
"",
"vector<node> trie;",
"",
"void push(string& s, int idx=0, int d=0){",
" if(d==s.length()) return;",
" if(trie[idx].nxt[s[d]-'a'] == -1){",
" trie.push_back(node(s[d]));",
" trie[idx].nxt[s[d]-'a'] = trie.size()-1;",
" }",
" push(s, trie[idx].nxt[s[d]-'a'], d+1);",
"}"
]
},
"trie2" : {
"prefix": "trie2",
"body": [
"struct node{",
" map<char, int> nxt;",
" char value;",
" bool isterm = false;",
"",
" node() {}",
" node(char v) : value(v) {}",
"};",
"",
"vector<node> trie;",
"",
"void push(string& s, int idx=0, int d=0){",
" if(d==s.length()) return;",
" if(trie[idx].nxt.find(s[d]) == trie[idx].nxt.end()){",
" trie.push_back(node(s[d]));",
" trie[idx].nxt[s[d]] = trie.size()-1;",
" }",
" push(s, trie[idx].nxt[s[d]], d+1);",
"}"
]
},
"dijkstra" : {
"prefix": "dijkstra",
"body": [
"const int sz=100'010;",
"int dist[sz];",
"vpi adj[sz];",
"",
"void dijk(int s){",
" priority_queue<pi, vpi, greater<>> pq;",
" fill(dist, dist+sz, inf);",
" dist[s]=0;",
" pq.emplace(0, s);",
"",
" while(!pq.empty()){",
" auto[cost, cur] = pq.top(); pq.pop();",
" if(dist[cur] != cost) continue;",
"",
" for(auto[nxt, c]:adj[cur]){",
" if(dist[nxt]>dist[cur]+c){",
" dist[nxt]=dist[cur]+c;",
" pq.emplace(dist[nxt], nxt);",
" }",
" }",
" }",
"}"
]
},
"lazyseg" : {
"prefix": "lazyseg",
"body": [
"const int sz=1<<20;",
"int tree[sz<<1];",
"int lazy[sz<<1];",
"",
"void init(){",
" for(int i=sz-1; i; i--) tree[i]=tree[i*2]+tree[i*2+1];",
"}",
"",
"void propagate(int s, int e, int idx){",
" if(lazy[idx] != 0){",
" if(s!=e){",
" lazy[idx*2] += lazy[idx];",
" lazy[idx*2+1] += lazy[idx];",
" }",
" tree[idx] += lazy[idx]*(e-s+1);",
" lazy[idx] = 0;",
" }",
"}",
"",
"void update(int l, int r, int k, int idx=1, int s=0, int e=sz-1){",
" propagate(s, e, idx);",
" if(l<=s && e<=r){",
" lazy[idx] = k;",
" propagate(s, e, idx);",
" return;",
" }",
" if(e<l || r<s) return;",
" int mid=s+e>>1;",
" update(l, r, k, idx*2, s, mid);",
" update(l, r, k, idx*2+1, mid+1, e);",
" tree[idx] = tree[idx*2]+tree[idx*2+1];",
"}",
"",
"int sum(int l, int r, int idx=1, int s=0, int e=sz-1){",
" propagate(s, e, idx);",
" if(l<=s && e<=r) return tree[idx];",
" if(e<l || r<s) return 0;",
" int mid=s+e>>1;",
" return sum(l, r, idx*2, s, mid)+sum(l, r, idx*2+1, mid+1, e);",
"}"
]
},
"articulation point" : {
"prefix": "cutvertex",
"body": [
"const int MAX=100'010;",
"vi adj[MAX];",
"int cnt, dfsn[MAX];",
"bool cut[MAX];",
"",
"int dfs(int cur, bool isroot=0){",
" int ret = dfsn[cur] = ++cnt;",
" int child=0;",
"",
" for(int nxt:adj[cur]){",
" if(!dfsn[nxt]){",
" child++;",
" int low=dfs(nxt);",
" if(low==dfsn[cur] && !isroot) cut[cur]=1;",
" ret=min(ret, low);",
" }",
" else ret=min(ret, dfsn[nxt]);",
" }",
"",
" if(isroot) cut[cur]=(child>=2);",
" return ret;",
"}"
]
},
"bridge" : {
"prefix": "bridge",
"body": [
"const int MAX=100'010;",
"vi adj[MAX];",
"int cnt, dfsn[MAX];",
"set<pi> s;",
"",
"int dfs(int cur, int prv=-1){",
" int ret=dfsn[cur]=++cnt;",
"",
" for(int nxt:adj[cur]){",
" if(prv==nxt) continue;",
" if(dfsn[nxt]) ret=min(ret, dfsn[nxt]);",
" else{",
" int low=dfs(nxt, cur);",
" if(low>dfsn[cur]) s.emplace(min(cur, nxt), max(cur, nxt));",
" ret=min(ret, low);",
" }",
" }",
"",
" return ret;",
"}"
]
},
"biconnected component" : {
"prefix": "bcc",
"body": [
"const int MAX=100'010;",
"vi adj[MAX];",
"int cnt, dfsn[MAX];",
"stack<pi> st;",
"vector<vpi> bcc;",
"",
"int dfs(int cur, int prv=-1){",
" int ret=dfsn[cur]=++cnt;",
"",
" for(int nxt:adj[cur]){",
" if(prv==nxt) continue;",
" if(dfsn[nxt]<dfsn[cur]) st.emplace(cur, nxt);",
"",
" if(dfsn[nxt]>0) ret=min(ret, dfsn[nxt]);",
" else{",
" int low=dfs(nxt, cur);",
" if(dfsn[cur]<=low){",
" vpi curb;",
" while(!st.empty() && st.top()!=pi(cur, nxt)){",
" curb.push_back(st.top());",
" st.pop();",
" }",
" curb.push_back(st.top());",
" st.pop();",
" bcc.push_back(curb);",
" }",
" ret=min(ret, low);",
" }",
" }",
"",
" return ret;",
"}"
]
},
"merge sort tree" : {
"prefix": "mergesorttree",
"body": [
"const int sz=1<<17;",
"vi tree[sz<<1];",
"",
"void init(){",
" for(int i=sz-1; i; i--){",
" tree[i].resize(tree[i*2].size() + tree[i*2+1].size());",
" merge(all(tree[i*2]), all(tree[i*2+1]), tree[i].begin());",
" }",
"}",
"",
"int query(int l, int r, int k, int idx=1, int s=0, int e=sz-1){",
" if(e<l || r<s) return 0;",
" if(l<=s && e<=r) return tree[idx].end() - upper_bound(all(tree[idx]), k);",
" int mid=s+e>>1;",
" return query(l, r, k, idx*2, s, mid) + query(l, r, k, idx*2+1, mid+1, e);",
"}"
]
},
"erathosthenes" : {
"prefix": "era",
"body": [
"const int MAX=100'010;",
"vi primes;",
"bool sieve[MAX+10] = {1, 1};",
"",
"void era(){",
" for(int i=2; i<=MAX; i++) if(!sieve[i]){",
" primes.push_back(i);",
" for(int j=i*i; j<=MAX; j+=i) sieve[j]=1;",
" }",
"}"
]
},
"mobius" : {
"prefix": "mobius",
"body": [
"const int MAX=100'010;",
"vi primes;",
"bool sieve[MAX+10] = {1, 1};",
"int mo[MAX+10] = {0, 1};",
"",
"void mobi(){",
" fill(mo, mo+MAX, 1);",
" for(int i=2; i<=MAX; i++) if(!sieve[i]){",
" mo[i]=-1;",
" for(int j=i*2; j<=MAX; j+=i){",
" sieve[j]=1;",
" mo[j]*=-1;",
" if(j/i%i==0) mo[j]=0;",
" }",
" }",
"}"
]
},
"matrix" : {
"prefix": "matrix",
"body": [
"template<typename T>",
"struct mat{",
" int r_sz, c_sz;",
" vector<vector<T>> board;",
"",
" static mat identity(int n){",
" mat ret(n, n);",
" for(int i=0; i<n; i++)",
" ret[i][i] = 1;",
" return ret;",
" }",
"",
" mat(int r, int c): r_sz(r), c_sz(c){",
" board.resize(r_sz, vector<T>(c_sz));",
" }",
" void print(){",
" for(int i=0; i<r_sz; i++){",
" for(int j=0; j<c_sz; j++)",
" cout<<board[i][j]<<' ';",
" cout<<endl;",
" }",
" cout<<endl;",
" }",
"",
" vector<T>& operator[](int _n){",
" return board[_n];",
" }",
" mat operator*(mat& p){",
" if(c_sz != p.r_sz) throw invalid_argument(\"invalid matrix size\");",
" mat ret(r_sz, p.c_sz);",
" for(int i=0; i<r_sz; i++)",
" for(int j=0; j<p.c_sz; j++)",
" for(int k=0; k<c_sz; k++){",
" ret[i][j] += board[i][k] * p[k][j];",
" }",
"",
" return ret;",
" }",
" mat operator+(mat& p){",
" if(r_sz != p.r_sz || c_sz != p.c_sz) throw invalid_argument(\"invalid matrix size\");",
" mat ret(r_sz, c_sz);",
" for(int i=0; i<r_sz; i++)",
" for(int j=0; j<c_sz; j++)",
" ret[i][j] = board[i][j] + p[i][j];",
" return ret;",
" }",
" mat operator-(mat& p){",
" if(r_sz != p.r_sz || c_sz != p.c_sz) throw invalid_argument(\"invalid matrix size\");",
" mat ret(r_sz, c_sz);",
" for(int i=0; i<r_sz; i++)",
" for(int j=0; j<c_sz; j++)",
" ret[i][j] = board[i][j] - p[i][j];",
" return ret;",
" }",
" mat operator+(T& p){",
" mat ret(r_sz, c_sz);",
" for(int i=0; i<r_sz; i++)",
" for(int j=0; j<c_sz; j++)",
" ret[i][j] = board[i][j] + p;",
" return ret;",
" }",
" mat operator-(T& p){",
" mat ret(r_sz, c_sz);",
" for(int i=0; i<r_sz; i++)",
" for(int j=0; j<c_sz; j++)",
" ret[i][j] = board[i][j] - p;",
" return ret;",
" }",
" mat operator*(T& p){",
" mat ret(r_sz, c_sz);",
" for(int i=0; i<r_sz; i++)",
" for(int j=0; j<c_sz; j++)",
" ret[i][j] = board[i][j] * p;",
" return ret;",
" }",
" mat operator/(T& p){",
" mat ret(r_sz, c_sz);",
" for(int i=0; i<r_sz; i++)",
" for(int j=0; j<c_sz; j++)",
" ret[i][j] = board[i][j] / p;",
" return ret;",
" }",
" mat operator%(T& p){",
" mat ret(r_sz, c_sz);",
" for(int i=0; i<r_sz; i++)",
" for(int j=0; j<c_sz; j++)",
" ret[i][j] = board[i][j] % p;",
" return ret;",
" }",
" mat operator^(int p){",
" if(r_sz != c_sz) throw invalid_argument(\"invalid matrix size\");",
" mat ret = mat::identity(r_sz);",
" mat a = *this;",
"",
" while(p){",
" if(p&1) ret = ret * a;",
" a = a * a;",
" p >>= 1;",
" }",
" return ret;",
" }",
"};"
]
},
"zz" : {
"prefix": "zz",
"body": [
"const int MAX=100'010;",
"int z[MAX];",
"",
"void zz(string str){",
" int n=str.size();",
" z[0]=n;",
" int l=0, r=0;",
"",
" for(int i=1; i<n; i++){",
" if(i<=r) z[i]=min(z[i-l], r-i+1);",
" while(z[i]+i<n && str[z[i]]==str[z[i]+i]) z[i]++;",
" if(i+z[i]-1 > r){",
" r=i+z[i]-1;",
" l=i;",
" }",
" }",
"}"
]
},
"manacher" : {
"prefix": "manacher",
"body": [
"const int MAX=200'010;",
"int m[MAX];",
"",
"void manacher(string str){",
" int p=0, r=0, n=str.size();",
" for(int i=1; i<n; i++){",
" if(i<=r) m[i]=min(r-i, m[2*p-i]);",
" while(i+m[i]+1<=n && i-m[i]-1>=0 && str[i+m[i]+1]==str[i-m[i]-1])",
" m[i]++;",
" if(i+m[i]>r){",
" p=i;",
" r=i+m[i];",
" }",
" }",
"}"
]
},
"kmp" : {
"prefix": "kmp",
"body": [
"const int MAX=100'010;",
"int fail[MAX];",
"",
"void kmp(string a, string b){",
" int A=a.size(), B=b.size();",
"",
" for(int i=1, j=0; i<B; i++){",
" while(j>0 && b[i]!=b[j]) j=fail[j-1];",
" if(b[i]==b[j]) fail[i] = ++j;",
" }",
"",
" for(int i=0, j=0; i<A; i++){",
" while(j>0 && a[i]!=b[j]) j=fail[j-1];",
" if(a[i]==b[j]){",
" if(j==B-1){",
" // found",
" loc.emplace_back(i-B+1, i);",
" j=fail[j];",
" }",
" else j++;",
" }",
" }",
"}"
]
},
"bellmanford" : {
"prefix": "bellmanford",
"body": [
"const int MAX=505;",
"int n, m, dist[MAX];",
"vpi adj[MAX];",
"",
"bool bellman_ford(int st){",
" fill(dist, dist+n+1, inf);",
" dist[st]=0;",
" ",
" for(int i=0; i<n; i++){",
" for(int j=1; j<=n; j++){",
" if(dist[j]==inf) continue;",
" for(auto[nxt, c]:adj[j]){",
" if(dist[nxt]>dist[j]+c){",
" dist[nxt]=dist[j]+c;",
" if(i==n-1){",
" return 0;",
" }",
" }",
" }",
" }",
" }",
" return 1;",
"}"
]
},
"combination" : {
"prefix": "combination",
"body": [
"const int MAX=2020, mod=1e9+7;",
"int dp[MAX][MAX];",
"",
"int combi(int n, int r){",
" if(r==0 || n==r) return 1;",
" int& ret=dp[n][r];",
" if(ret!=-1) return ret;",
" return ret=(combi(n-1, r-1)+combi(n-1, r))%mod;",
"}"
]
},
"small to large" : {
"prefix": "smalltolarge",
"body" : [
"const int MAX=200'010;",
"set<int> s[MAX];",
"",
"// b를 a에",
"void join(int a, int b){",
" if(s[a].size()<s[b].size()) swap(s[a], s[b]);",
" for(int elem:s[b]) s[a].insert(elem);",
" s[b].clear();",
"}"
]
},
"geometry" : {
"prefix": "geometry",
"body": [
"const pi O={0, 0};",
"pi operator + (const pi& l, const pi& r){ return pi(l.X + r.X, l.Y + r.Y); }",
"pi operator - (const pi& l, pi r){ return pi(l.X - r.X, l.Y - r.Y); }",
"int operator * (const pi& l, const pi& r){ return l.X * r.X + l.Y * r.Y; }",
"int operator / (const pi& l, const pi& r){ return l.X * r.Y - l.Y * r.X; }",
]
},
"angular sort" : {
"prefix": "anglesort",
"body": [
"inline int quad(const pi& a){",
" auto[x, y]=a;",
" if(x>=0 && y>0) return 1;",
" else if(x<0 && y>=0) return 2;",
" else if(x<=0 && y<0) return 3;",
" else return 4;",
"}",
"",
"void angsort(vpi& ps){",
" sort(all(ps), [](pi a, pi b){",
" a=a-O; b=b-O;",
" return quad(a)==quad(b) ? a/b>0 : quad(a)<quad(b);",
" });",
"}"
]
},
"quadrant" : {
"prefix": "quadrant",
"body": [
"inline int quad(const pi& a){",
" auto[x, y]=a;",
" if(x>=0 && y>0) return 1;",
" else if(x<0 && y>=0) return 2;",
" else if(x<=0 && y<0) return 3;",
" else return 4;",
"}"
]
},
"distance" : {
"prefix": "distance",
"body": [
"int dist(const pi& a, const pi& b){",
" return (b.X-a.X)*(b.X-a.X) + (b.Y-a.Y)*(b.Y-a.Y);",
"}"
]
},
"rotating calipers" : {
"prefix": "rotatingcalipers",
"body": [
"int dist(const pi& a, const pi& b){",
" return (b.X-a.X)*(b.X-a.X) + (b.Y-a.Y)*(b.Y-a.Y);",
"}",
"",
"tp rotating_calipers(const vpi& hull){",
" int sz = hull.size();",
" if(sz==1) return {0, 0, 0};",
" int c1=0, c3=1, i=0, j=1;",
" int m=dist(hull[i], hull[j]);",
" bool end=0;",
" if(sz==2) return {m, i, j};",
"",
" while(1){",
" int c2=(c1+1)%sz, c4=(c3+1)%sz;",
" int w=(hull[c2]-hull[c1])/(hull[c4]-hull[c3]);",
"",
" if(w>0){",
" c3=(c3+1)%sz;",
" }",
" else{",
" c1=(c1+1)%sz;",
" if(c1==0) break;",
" }",
"",
" int d=dist(hull[c1], hull[c3]);",
" if(d>m){",
" m=d;",
" i=c1;",
" j=c3;",
" }",
" }",
"",
" return tp(m, i, j);",
"}"
]
},
"area" : {
"prefix": "area",
"body": [
"double area(const vpi& p){",
" int sz=p.size(), ret=0;",
" for(int i=2; i<sz; i++){",
" ret += (p[i]-p[0])/(p[i-1]-p[0]);",
" }",
" return (double)abs(ret)/2;",
"}"
]
},
"iscross" : {
"prefix": "iscross_ls_ls",
"body": [
"int iscross(pi a, pi b, pi c, pi d){",
" if(a>b) swap(a, b);",
" if(c>d) swap(c, d);",
" int abc=ccw(a, b, c), abd=ccw(a, b, d);",
" int cda=ccw(c, d, a), cdb=ccw(c, d, b);",
"",
" // 일직선",
" if(abc==0 && abd==0){",
" if(b<c || d<a) return 0;",
" else return 1;",
" }",
" // 일직선이 아님",
" else if(abc*abd<=0 && cda*cdb<=0) return 1;",
" else return 0;",
"}"
]
},
"iscross_ls_p" : {
"prefix": "iscross_ls_p",
"body": [
"bool iscross(pi a, pi b, pi c){",
" if(a>b) swap(a, b);",
" return ccw(a, b, c)==0 && a<=c && c<=b;",
"}"
]
},
"inside_concave" : {
"prefix": "is_inside_concave",
"body": [
"int is_inside_concave(const vpi& p, pi q){",
" // 겹치는지 확인",
" for(int i=0; i<n; i++){",
" int j=(i+1)%n;",
" if(iscross(p[i], p[j], q)) return 1;",
" }",
" // 완전히 내부일 때",
" int cnt=0;",
" for(int i=0; i<n; i++){",
" int j=(i+1)%n;",
" if(iscross(p[i], p[j], q, pi(inf, q.Y+1))) cnt++;",
" }",
" return cnt%2;",
"}"
]
},
"inside_convex" : {
"prefix": "is_inside_convex",
"body": [
"int is_inside_convex(const vpi& p, pi q){",
" int sz = p.size();",
" if(ccw(p[0], p[1], q)<0 || ccw(p[0], p[sz-1], q)>0) return 0;",
"",
" int st=1, en=sz-1;",
" while(st+1<en){",
" int mid=st+en>>1;",
" if(ccw(p[0], p[mid], q)>=0) st=mid;",
" else en=mid;",
" }",
"",
" if(ccw(p[st], p[(st+1)%sz], q)>=0) return 1;",
" else return 0;",
"}"
]
},
"closest_pair" : {
"prefix": "closest_pair",
"body": [
"int closest_pair(vpi& p){",
" int sz = p.size();",
" sort(all(p));",
" set<pi> s;",
" s.emplace(p[0].Y, p[0].X);",
" s.emplace(p[1].Y, p[1].X);",
"",
" int ans=dist(p[0], p[1]), pos=0;",
" for(int i=2; i<sz; i++){",
" while(pos < i){",
" if((p[i].X-p[pos].X) * (p[i].X-p[pos].X) <= ans) break;",
" s.erase({p[pos].Y, p[pos].X});",
" pos++;",
" }",
"",
" auto left = s.lower_bound({p[i].Y - (int)sqrt(ans), -inf});",
" auto right = s.upper_bound({p[i].Y + (int)sqrt(ans), inf});",
" for(auto it=left; it!=right; it++){",
" ans = min(ans, dist({ it->Y, it->X }, p[i]));",
" }",
"",
" s.insert({p[i].Y, p[i].X});",
" }",
"",
" return ans;",
"}"
]
},
"ternary search" : {
"prefix": "ternary_search",
"body": [
"int func(int x){",
"}",
"",
"// func는 위로 볼록",
"int ternary_search(){",
" int st=0, en=inf;",
" while(st+2<en){",
" int a=st+en>>1, b=a+1;",
" if(func(a)>func(b)) en=b;",
" else st=a;",
" }",
"",
" int ans=st;",
" for(int i=st; i<=en; i++) if(func(ans)<func(i)) ans=i;",
" return ans;",
"}"
]
},
"edmond karp" : {
"prefix": "edmondkarp",
"body": [
"const int MAX=404;",
"int n;",
"int f[MAX][MAX], c[MAX][MAX], pre[MAX];",
"int s, e;",
"vi adj[MAX];",
"",
"int bfs(){",
" mset(pre, -1);",
" queue<int> q;",
" q.push(s);",
" pre[s]=0;",
"",
" while(!q.empty()){",
" int cur=q.front();",
" q.pop();",
"",
" for(int nxt:adj[cur]){",
" if(pre[nxt]==-1 && c[cur][nxt]-f[cur][nxt]>0){",
" pre[nxt]=cur;",
" q.push(nxt);",
" }",
" }",
" }",
" if(pre[e]==-1) return 0;",
"",
" int flow=inf;",
" for(int i=e; i!=s; i=pre[i]) flow=min(flow, c[pre[i]][i]-f[pre[i]][i]);",
" for(int i=e; i!=s; i=pre[i]) f[pre[i]][i]+=flow, f[i][pre[i]]-=flow;",
" return flow;",
"}"
]
},
"bipartite matching" : {
"prefix": "bipartite_matching",
"body": [
"const int MAX=404;",
"int n, m;",
"int A[MAX], B[MAX];",
"int vis[MAX];",
"vi adj[MAX];",
"",
"int match(int a, int k){",
" vis[a]=k;",
"",
" for(int b:adj[a]) if(B[b]==-1 || vis[B[b]]!=k && match(B[b], k)){",
" A[a]=b;",
" B[b]=a;",
" return 1;",
" }",
" return 0;",
"}"
]
},
"npow" : {
"prefix": "npow",
"body": [
"int npow(int n, int r){",
" if(r==0) return 1;",
" int t=npow(n, r/2);",
" if(r%2) return t*t%mod*n%mod;",
" else return t*t%mod;",
"}"
]
},
"LCA" : {
"prefix": "LCA",
"body": [
"struct LCA {",
" static const int MAX=N;",
" int par[18][MAX], dept[MAX];",
" vi adj[MAX];",
"",
" void dfs(int cur, int prv=-1){",
" for(int nxt:adj[cur]){",
" if(nxt==prv) continue;",
" par[0][nxt]=cur;",
" dept[nxt]=dept[cur]+1;",
" dfs(nxt, cur);",
" }",
" }",
"",
" void sparse(){",
" for(int i=1; i<18; i++){",
" for(int j=1; j<MAX; j++){",
" par[i][j]=par[i-1][par[i-1][j]];",
" }",
" }",
" }",
"",
" int lca(int a, int b){",
" if(dept[a]>dept[b]) swap(a, b);",
"",
" int d=dept[b]-dept[a];",
" for(int i=0; d; i++){",
" if(d%2==1) b=par[i][b];",
" d/=2;",
" }",
" if(a==b) return a;",
"",
" for(int i=17; i>=0; i--){",
" if(par[i][a] != par[i][b]){",
" a=par[i][a];",
" b=par[i][b];",
" }",
" }",
" return par[0][a];",
" }",
"",
" void init(){",
" dfs(1);",
" sparse();",
" }",
"",
" int dist(int a, int b){",
" int anc = lca(a, b);",
" return dept[a]+dept[b]-2*dept[anc];",
" }",
"",
" vi &operator[] (int k) { return adj[k]; }",
"} tree;"
]
},
"FFT" : {
"prefix": "FFT",
"body": [
"void FFT(vcp &f, cpx w){",
" int sz=sz(f);",
" if(sz==1) return;",
"",
" vcp even(sz>>1), odd(sz>>1);",
" forr(i, sz){",
" if(i&1) odd[i>>1] = f[i];",
" else even[i>>1] = f[i];",
" }",
" FFT(even, w*w); FFT(odd, w*w);",
"",
" cpx wc(1, 0);",
" forr(i, sz/2){",
" f[i] = even[i]+wc*odd[i];",
" f[i+sz/2] = even[i]-wc*odd[i];",
" wc *= w;",
" }",
"}",
"",
"vcp mul(vcp a, vcp b){",
" int sz=1;",
" while(sz<sz(a) || sz<sz(b)) sz<<=1;",
" sz<<=1;",
" a.resize(sz); b.resize(sz);",
"",
" cpx w(cos(2*PI/sz), sin(2*PI/sz));",
" vcp c(sz);",
" FFT(a, w); FFT(b, w);",
" forr(i, sz) c[i]=a[i]*b[i];",
"",
" FFT(c, cpx(w.real(), -w.imag()));",
" forr(i, sz){",
" c[i] /= sz;",
" c[i] = cpx(round(c[i].real()), round(c[i].imag()));",
" }",
" return c;",
"}"
]
},
"HLD" : {
"prefix": "HLD",
"body": [
"struct HLD{",
" int n;",
" int sz[N], in[N], out[N], top[N], dep[N], par[N];",
" int cnt;",
" vi adj[N];",
"",
" void hld(int x, int p = -1) {",
" sz[x] = 1;",
" // Remove par node",
" forr(i, sz(adj[x])){",
" int nxt = adj[x][i];",
" if(nxt == p){",
" adj[x].erase(adj[x].begin() + i);",
" break;",
" }",
" }",
" // hld",
" for(auto& i:adj[x]){",
" dep[i] = dep[x] + 1;",
" par[i] = x;",
" hld(i, x);",
" sz[x] += sz[i];",
"",
" if(sz[adj[x][0]] < sz[i]) swap(adj[x][0], i);",
" }",
" }",
"",
" void ett(int x){",
" in[x] = ++cnt;",
" for(int i:adj[x]){",
" top[i] = (adj[x][0] == i) ? top[x] : i;",
" ett(i);",
" }",
" out[x] = cnt;",
" }",
"",
" int query(int a, int b){",
" int ret = 0;",
" while(top[a] != top[b]){",
" if(dep[top[a]] > dep[top[b]]) swap(a, b);",
" // Query from in[top[b]] to in[b]",
" b = par[top[b]];",
" }",
"",
" if(dep[a] > dep[b]) swap(a, b);",
" // Query from in[a] to in[b]",
" return ret;",
" }",
"",
" int lca(int a, int b){",
" while(top[a] != top[b]){",
" if(dep[top[a]] > dep[top[b]]) swap(a, b);",
" b = par[top[b]];",
" }",
" return dep[a] < dep[b] ? a : b;",
" }",
"",
" void makeEdge(int a, int b) { ",
" adj[a].push_back(b); ",
" adj[b].push_back(a); ",
" }",
"",
" void init(int _n){",
" n = _n;",
"",
" // forr(i, n-1){",
" // int a, b;",
" // cin>>a>>b;",
" // makeEdge(a, b);",
" // }",
"",
" hld(1);",
" ett(1);",
" }",
"} tree;"
]
}
}
/*
struct HLD{
int n, m;
int sz[N], in[N], out[N], top[N], dep[N], par[N];
int cnt;
vi adj[N];
void hld(int x, int p = -1) {
sz[x] = 1;
// Remove par node
forr(i, sz(adj[x])){
int nxt = adj[x][i];
if(nxt == p){
adj[x].erase(adj[x].begin() + i);
break;
}
}
// hld
for(auto& i:adj[x]){
dep[i] = dep[x] + 1;
par[i] = x;
hld(i, x);
sz[x] += sz[i];
if(sz[adj[x][0]] < sz[i]) swap(adj[x][0], i);
}
}
void ett(int x){
in[x] = ++cnt;
for(int i:adj[x]){
top[i] = (adj[x][0] == i) ? top[x] : i;
ett(i);
}
out[x] = cnt;
}
int query(int a, int b){
int ret = 0;
while(top[a] != top[b]){
if(dep[top[a]] > dep[top[b]]) swap(a, b);
// Query from in[top[b]] to in[b]
b = par[top[b]];
}
if(dep[a] > dep[b]) swap(a, b);
// Query from in[a] to in[b]
return ret;
}
int lca(int a, int b){
while(top[a] != top[b]){
if(dep[top[a]] > dep[top[b]]) swap(a, b);
b = par[top[b]];
}
return dep[a] < dep[b] ? a : b;
}
void makeEdge(int a, int b) {
adj[a].push_back(b);
adj[b].push_back(a);
}
void init(int _n, int _m){
n = _n;
m = _m;
// forr(i, m){
// int a, b;
// cin>>a>>b;
// makeEdge(a, b);
// }
}
} tree;
*/