Sumário

• Estruturas de Dados
  • Segment Tree
    • Point update
    • Lazy propagation
  • Fenwick Tree / BIT
    • BIT 2D
  • Sparse Table
  • SQRT Decomposition
  • Trie
  • Union Find
  • Ordered Set
• Grafos
  • Dijkstra
  • Bellman-Ford
  • Floyd-Warshall
  • Pontes e Pontos de Articulação
  • Componentes Fortemente Conexos
  • Ordenação Topológica
  • Minimum Spanning Tree
  • Lowest Common Ancestor
  • Bipartite Matching
  • Fluxo Máximo
    • Edmons-Karp
• Strings
  • KMP
  • Z Function
  • Suffix Array
• Matemática
  • MDC e MMC
  • Euclides Extendido
  • Inverso Multiplicativo
  • Crivo de Erastóstenes
    • Crivo segmentado
  • Totiente de Euler
  • Exponenciação de Matrizes
  • Miller-Rabin + Pollard's Rho
• Geometria Computacional
  • Interseção de Retas
  • Outras Operações com Ponto e Reta
  • Operações com Vetores
  • Interseção de Segmentos
  • Área de Polígono
  • Convex Hull
  • Par de Pontos Mais Próximos
  • Ponto Dentro do Polígono

Estruturas de dados

Segment Tree

Point update

https://leetcode.com/problems/range-sum-query-mutable/description/

Range Sum Query

structSegmentTree {
vector<int>tree;
ints, e;
SegmentTree(ints, inte, intval=0): s(s), e(e) {
intsz=e-s+1;
tree=vector<int>(4*sz, val);
}
SegmentTree(vector<int>&v) {
*this=SegmentTree(0, v.size() -1);
build(v, 1, s, e);
}
voidbuild(vector<int>&v, inti, inta, intb) {
if(a==b)
tree[i] =v[a];
else {
intm= (a+b) >> 1;
build(v, 2*i, a, m);
build(v, 2*i+1, m+1, b);
tree[i] =tree[2*i] +tree[2*i+1];
}
}
voidupdate(intp, intval, inti, inta, intb) {
if(a>p||b<p) return;
if(a==b&&p==a)
tree[i] =val;
else {
intm= (a+b) >> 1;
update(p, val, 2*i, a, m);
update(p, val, 2*i+1, m+1, b);
tree[i] =tree[2*i] +tree[2*i+1];
}
}
intquery(intA, intB, inti, inta, intb) {
if(a>B||b<A) return0;
if(a >= A&&b <= B) returntree[i];
intm= (a+b) >> 1;
returnquery(A, B, 2*i, a, m) +query(A, B, 2*i+1, m+1, b);
}
voidupdate(intp, intval) {
update(p, val, 1, s, e);
}
intquery(intA, intB) {
returnquery(A, B, 1, s, e);
}
};

Lazy propagation

https://www.urionlinejudge.com.br/judge/pt/problems/view/1500

Range Sum Query

structSegmentTree {
vector<ll>tree, lazy;
ints, e;
SegmentTree(ints, inte): s(s), e(e) {
intsz=e-s+1;
tree=lazy=vector<ll>(4*sz, 0);
}
SegmentTree(vector<ll>&v) {
*this=SegmentTree(0, v.size() -1);
build(v, 1, s, e);
}
voidbuild(vector<ll>&v, inti, inta, intb) {
lazy[i] =0;
if(a==b)
tree[i] =v[i];
else {
intm= (a+b) >> 1;
build(v, 2*i, a, m);
build(v, 2*i+1, m+1, b);
tree[i] =tree[2*i] +tree[2*i+1];
}
}
voidpropagate(inti, inta, intb) {
if(!lazy[i]) return;
tree[i] += (b-a+1) *lazy[i];
if(a!=b) {
lazy[2*i] +=lazy[i];
lazy[2*i+1] +=lazy[i];
}
lazy[i] =0;
}
voidupdate(intA, intB, llval, inti, inta, intb) {
propagate(i, a, b);
if(a>B||b<A) return;
if(a >= A&&b <= B) {
tree[i] += (b-a+1) *val;
if(a!=b) {
lazy[2*i] +=val;
lazy[2*i+1] +=val;
}
}
else {
intm= (a+b) >> 1;
update(A, B, val, 2*i, a, m);
update(A, B, val, 2*i+1, m+1, b);
tree[i] =tree[2*i] +tree[2*i+1];
}
}
llquery(intA, intB, inti, inta, intb) {
if(a>B||b<A) return0;
propagate(i, a, b);
if(a >= A&&b <= B) returntree[i];
intm= (a+b) >> 1;
returnquery(A, B, 2*i, a, m) +query(A, B, 2*i+1, m+1, b);
}
voidupdate(intA, intB, llval) {
update(A, B, val, 1, s, e);
}
llquery(intA, intB) {
returnquery(A, B, 1, s, e);
}
};

BIT

https://www.urionlinejudge.com.br/judge/pt/problems/view/2857

structBit { //1-indexadointn;
vector<int>arr;
intlsone(intx) {
returnx&-x;
}
Bit(intN, intval=0): n(N+1) {
arr=vector<int>(N+1, val);
}
Bit(vector<int>&v) {
*this=Bit(v.size());
for (inti=1; i <= n; ++i)
update(v[i], i);
}
voidupdate(intpos, intval) {
for (; pos<n; pos+=lsone(pos))
arr[pos] +=val;
}
intget(intpos) {
intsum=0;
for (; pos>0; pos-=lsone(pos))
sum+=arr[pos];
returnsum;
}
intget(inta, intb) {
returnget (b) -get(a-1);
}
};

BIT 2D

https://www.urionlinejudge.com.br/judge/pt/problems/view/1112

intbit[MAX][MAX];
voidupdate(intx, inty, intval) {
for(inti=x; i<MAX; i+=i&-i)
for(intj=y; j<MAX; j+=j&-j)
bit[i][j] +=val;
}
intget(intx, inty) {
intans=0;
for(inti=x; i>0; i-=i&-i)
for(intj=y; j>0; j-=j&-j)
ans+=bit[i][j];
returnans;
}
intget(intx1, inty1, intx2, inty2) {
if(x1>x2) swap(x1, x2);
if(y1>y2) swap(y1, y2);
returnget(x2, y2) -get(x1-1, y2) -get(x2, y1-1) +get(x1-1, y1-1);
}

Sparse Table

https://www.spoj.com/problems/RMQSQ/

Range Minimum Query

#defineMAX 100100
#defineLOG_MAX 20
intv[MAX];
inttable[MAX][LOG_MAX];
voidbuild(intn) {
for(inti=0; i<n; ++i)
table[i][0] =v[i];
for(inti=1; i<LOG_MAX; ++i)
for(intj=0; j<MAX; ++j)
table[j][i] =min(table[j][i-1], table[min(n-1, j+ (1 << (i-1)))][i-1]);
}
intget_min(inti, intj) {
intd=log2(j-i+1); returnmin(table[i][d], table[j- (1 << d) +1][d]);
}

SQRT Decomposition

https://www.urionlinejudge.com.br/judge/pt/problems/view/2800

constintMAXR=350; //raiz sempre fixaconstintMAXN=100010;
intbucket[MAXR][MAXN];
intarr[MAXN];
// Altera o valor da posição id para xvoidupdate(intid, intx){
intbloco=id / MAXR;
bucket[bloco][arr[id]]--;
bucket[bloco][x]++;
arr[id] =x;
}
// A query retorna o número de valores iguais a W no intervalo A - Bintquery(intA, intB, intW){
intb1=A/MAXR;
intb2=B/MAXR;
intcnt=0;
if(b1==b2){
for(inti=A; i <= B; i++){
if(arr[i] ==W) cnt++;
}
}
else{
for(inti=b1+1; i <= b2-1; i++)
cnt+=bucket[i][W];
for(inti=A; i< (b1+1) *MAXR; i++)
if(arr[i] ==W) cnt++;
for(inti=b2*MAXR; i <= B; i++)
if(arr[i] ==W) cnt++;
}
returncnt;
}

Trie

https://www.spoj.com/problems/STRMATCH/

Versão recursiva

structTrie {
intcnt=0; // numero de prefixos que terminam neste noTrie*c[26];
Trie() {
memset(c, 0, sizeofc);
}
// insere s[i..] na trievoidinsert(string&s, inti=0) {
++cnt;
if(i >= s.length()) return;
if(c[s[i] -'a'] ==NULL)
c[s[i] -'a'] =newTrie();
c[s[i] -'a']->insert(s, i+1);
}
// retorna o numero de prefixos iguais a sintcount(string&s, inti=0) {
if(i==s.length()) returncnt;
if(c[s[i] -'a'] ==NULL) return0;
returnc[s[i] -'a']->count(s, i+1);
}
};

Versão iterativa

structNode{
Node*children[26];
intisEnd;
Node(){
for(inti=0; i<26; i++){
children[i] = NULL;
}
isEnd=0;
}
};
structTrie{
Node*root=newNode();
voidinsert(conststring&s, intini) {
Node*it=root;
for(inti=ini; i< (int)s.size(); i++){
charc=s[i];
if(!it->children[c-'a']){
it->children[c-'a'] =newNode();
}
it=it->children[c-'a'];
it->isEnd++;
} }
intsearch(conststring&s){
Node*it=root;
intvezes=0;
for(auto c: s){
if(it->children[c-'a'] == NULL)
return0;
it=it->children[c-'a'];
}
returnit->isEnd;
}
};

Union Find

https://www.hackerearth.com/practice/data-structures/disjoint-data-strutures/basics-of-disjoint-data-structures/practice-problems/algorithm/count-friends/

typedefvector<int>vi;
structUnionFind {
vip, sz;
intn;
UnionFind(intn): n(n), p(vi(n, 0)), sz(vi(n, 1)) {
for(inti=0; i<n; ++i)
p[i] =i;
}
intfind(intv) {
returnp[v] ==v ? v : v=find(p[v]);
}
voiduni(intu, intv) {
u=find(u), v=find(v);
if(u==v) return;
if(sz[v] >sz[u]) swap(u, v);
p[v] =u, sz[u] +=sz[v];
}
intsize(intv) {
returnsz[find(v)];
}
};

Ordered Set

http://codeforces.com/blog/entry/11080?locale=en

#include<ext/pb_ds/assoc_container.hpp>#include<ext/pb_ds/tree_policy.hpp>usingnamespace__gnu_pbds;
typedeftree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>ordered_set;
// st.find_by_order(k) - iterador para o k-ésimo menor elemento (0-indexado)// st.order_by_key(x) - número de elementos menores que x

Grafos

Dijkstra

https://www.hackerrank.com/challenges/dijkstrashortreach/problem

intdist[MAX];
intdijkstra(intorig, intdest) {
memset(dist, 0x3f, sizeofdist);
dist[orig] =0;
priority_queue<pii>pq;
pq.push(pii(0, orig));
while(!pq.empty()) {
auto p=pq.top(); pq.pop();
intd=-p.first;
intu=p.second;
if(u==dest) returnd;
if(d>dist[u]) continue;
for(auto v : g[u])
if(d+v.second<dist[v.first]) {
dist[v.first] =d+v.second;
pq.push(pii(-dist[v.first], v.first));
}
}
return-1;
}

Bellman-Ford

https://practice.geeksforgeeks.org/problems/negative-weight-cycle/0

#defineINF 0x3f3f3f3f
structEdge { intu, v, w; } edges[MAXM];
intn, m, d[MAXN];
// retorna true se não houver ciclo negativoboolbellman_ford(ints) {
memset(d, 0x3f, sizeofd);
d[s] =0;
boolok= true; // indica se relaxou alguma arestafor(intk=0; k<n-1&&ok; ++k) {
ok= false;
for(inti=0; i<m; ++i) {
auto e=edges[i];
if(d[e.v] >d[e.u] +e.w)
d[e.v] =d[e.u] +e.w, ok= true;
}
}
for(inti=0; i<m; ++i) {
auto e=edges[i];
if(d[e.v] >d[e.u] +e.w)
return false;
}
return true;
}

Floyd-Warshall

https://practice.geeksforgeeks.org/problems/implementing-floyd-warshall/0

intg[MAX][MAX]; // g[i][i] = INFintdist[MAX][MAX];
voidfloyd(intn) {
for(inti=0; i<n; ++i)
for(intj=0; j<n; ++j)
dist[i][j] =g[i][j];
for(intk=0; k<n; ++k)
for(inti=0; i<n; ++i)
for(intj=0; j<n; ++j)
dist[i][j] =min(dist[i][j], dist[i][k] +dist[k][j]);
}

Pontes e Pontos de Articulação

constintMAXN=550;
intd[MAXN], low[MAXN], tempo=0, raiz;
/*d[u] é o tempo de descoberta de ulow[u] é o menor d de um descendente próprio de u*/vector<int>adj[MAXN];
vector<int>vertices_corte;
vector<pair<int, int>>pontes;
voiddfs(intu, intp){
intnf=0;
boolany= false;
d[u] =low[u] =++tempo;
for(intv: adj[u]){
if(!d[v]){
dfs(v, u);
nf++;
if(low[v] >= d[u]) any= true;
low[u] =min(low[u], low[v]);
if(low[v] >d[u]){
// u-v é uma pontepontes.push_back({v, u});
}
}
elseif(v!=p){
low[u] =min(low[u], d[v]);
}
}
if( (u==raiz&&nf >= 2) || (u!=raiz&&any) ){
// u é um vértice de cortevertices_corte.push_back(u);
}
}

Componentes Fortemente Conexos

intd[MAX], low[MAX], tempo, pilha[MAX], topo=-1, cont=0, comp[MAX];
llimemo[MAX];
vector<int>g[MAX];
voiddfs(intu) {
pilha[++topo] =u;
low[u] =d[u] =++tempo;
for(inti=0; i< (int)g[u].size(); i++) {
intv=g[u][i];
if(!d[v]) {
dfs(v);
low[u] =min(low[u], low[v]); }
elselow[u] =min(low[u], d[v]);
}
if(d[u] ==low[u]) {
intx;
++cont;
do {
x=pilha[topo--];
comp[x] =cont;
d[x] =5*MAX; //equivalente a d[x] = INF
} while(x!=u);
}
}

Ordenação Topológica

https://olimpiada.ic.unicamp.br/pratique/p2/2011/f2/escalona/

voidbfs(vector<int>&ans){
priority_queue<int>pq;
for(inti=0; i<n; i++) if(!grau[i]) pq.push(-i);
while(!pq.empty()){
intv=-pq.top(); pq.pop();
ans.push_back(v);
for(intu: adj[v]){
if(grau[u]){
grau[u]--;
if(!grau[u]) pq.push(-u);
}
}
}
}

Minimum Spanning Tree

https://www.urionlinejudge.com.br/judge/pt/problems/view/2404

structAresta {
intu, v, peso;
};
boolcomp(Arestaa, Arestab) {
returna.peso<b.peso;
}
intkruskal(vector<Aresta>&arestas, intn) {
sort(arestas.begin(), arestas.end(), comp);
intsoma=0;
UnionFinduf(n);
for(Arestaaresta: arestas) {
intv=uf.find(aresta.v);
intu=uf.find(aresta.u);
intpeso=aresta.peso;
if(v!=u) {
soma+=peso;
uf.uni(v, u);
}
}
returnsoma;
}

Lowest Common Ancestor

https://www.spoj.com/problems/LCA/

#defineMAX 100100
#defineLOG_MAX 20
vector<int>g[MAX];
intanc[MAX][LOG_MAX], h[MAX];
voiddfs(intu, intp, inthu) {
if(h[u] >-1) return;
h[u] =hu;
anc[u][0] =p;
for(auto v : g[u])
dfs(v, u, hu+1);
}
voidbuild(intn) {
memset(h, -1, sizeofh);
dfs(1, 0, 0);
for(inti=1; i<LOG_MAX; ++i)
for(intv=1; v <= n; ++v)
anc[v][i] =anc[ anc[v][i-1] ][i-1];
}
intlca(intu, intv) {
if(h[u] >h[v]) swap(u, v);
for(inti=LOG_MAX-1; i >= 0; --i)
if(h[v] -h[u] >= (1 << i))
v=anc[v][i];
if(u==v) returnu;
for(inti=LOG_MAX-1; i >= 0; --i)
if(anc[u][i] !=anc[v][i])
u=anc[u][i], v=anc[v][i];
returnanc[u][0];
}

Bipartite Matching

Fluxo Máximo

Edmons-Karp

https://practice.geeksforgeeks.org/problems/find-the-maximum-flow/0

intn, g[MAXN][MAXN], gr[MAXN][MAXN], f[MAXN][MAXN], p[MAXN];
voidbfs(ints, intt) {
queue<int>q;
memset(p, -1, sizeofp);
q.push(s);
while(!q.empty() &&p[t] ==-1) {
intu=q.front(); q.pop();
for(intv=0; v<n; ++v)
if(gr[u][v] &&p[v] ==-1)
q.push(v), p[v] =u;
}
}
intedmons_karp(ints, intt) {
memset(f, 0, sizeoff);
memcpy(gr, g, sizeofgr);
for(bfs(s, t); p[t] !=-1; bfs(s, t)) {
intmn=INT_MAX;
for(intv=t; v!=s; v=p[v])
mn=min(mn, gr[p[v]][v]);
for(intv=t; v!=s; v=p[v]) {
intu=p[v];
gr[u][v] -=mn;
gr[v][u] +=mn;
if(g[u][v] >0) f[u][v] +=mn;
elsef[v][u] -=mn;
}
}
intans=0;
for(inti=0; i<n; ++i)
ans+=f[s][i] -f[i][s];
returnans;
}

Strings

KMP

https://www.urionlinejudge.com.br/judge/pt/problems/view/2651

intlps[MAXM];
voidkmppp(string&p) {
inti=0, j=-1;
lps[0] =-1;
while(i<p.size()) {
while(j >= 0&&p[i] !=p[j]) j=lps[j];
i++, j++;
lps[i] =j;
}
}
intkmp(string&p, string&t) {
inti=0, j=0, ans=0;
while(i<t.size()) {
while(j >= 0&&t[i] !=p[j]) j=lps[j];
i++, j++;
if(j==p.size()) // matchj=lps[j], ++ans;
}
returnans;
}

Z Function

https://practice.geeksforgeeks.org/problems/search-pattern/0

voidzf(string&s, vector<int>&z) {
intL=0, R=0, n=s.length(); z.resize(n);
z[0] =n;
for(inti=1; i<n; ++i) {
if(R<i) {
for(L=R=i; R<n&&s[R] ==s[R-L]; ++R);
z[i] =R-L;
--R;
}
elseif(z[i-L] <= R-i)
z[i] =z[i-L];
else {
for(L=i, ++R; R<n&&s[R] ==s[R-L]; ++R);
z[i] =R-L;
--R;
}
}
}

Suffix Array

Matemática

MDC e MMC

https://practice.geeksforgeeks.org/problems/lcm-and-gcd/0

// __gcd(a, b)intmdc(inta, intb) {
returnb ? mdc(b, a % b) : a;
}
intmmc(inta, intb) {
returna / mdc(a, b) *b;
}

Euclides Extendido

// x * a + y * b = mdc(a, b)intmdc(inta, intb, int&x, int&y) {
if(b==0) {
x=1, y=0;
returna;
}
intx2, y2;
intm=mdc(b, a % b, x2, y2);
x=y2;
y=x2- (a / b) *y2;
returnm;
}

Inverso Multiplicativo

// m primo => invMod(a, m) = a^(m-2) (mod m)intinvMod(inta, intm) {
intx, y;
if(mdc(a, m, x, y) !=1) return-1; // não existe inverso return (x % m+m) % m;
}

Crivo de Erastóstenes

https://practice.geeksforgeeks.org/problems/sieve-of-eratosthenes/0/

intp[MAX], np;
boolisPrime[MAX];
voidcrivo() {
p[np++] =2;
isPrime[2] = false;
for (inti=3; i<MAX; i+=2)
isPrime[i] = true;
for (inti=3; i<MAX; i+=2)
if (isPrime[i]) {
p[np++] =i;
for (intj=2*i; j<MAX; j+=i)
isPrime[j] = false;
}
}

Crivo segmentado

https://www.spoj.com/problems/PRINT/

// Primeiro gerar crivo até sqrt(maior valor)// Adiciona todos os primos no intervalo [l, u] em ansvoidprimes(intl, intu, vector<int>&ans) {
vector<bool>prime(u-l+1, true);
if (l<1) prime[0] = false;
if (l<2) prime[1-l] = false;
for (inti=0; i<np&&p[i] <= u; ++i) {
intstart= (l>1 ? p[i] * (l / p[i]) : 2*p[i]);
while (start<l||start==p[i]) start+=p[i];
for (intj=start; j <= u; j+=p[i])
prime[j-l] = false;
}
for (inti=0; i<prime.size(); ++i)
if (prime[i])
ans.push_back(i+l);
}

Totiente de Euler

https://practice.geeksforgeeks.org/problems/euler-totient-function/0/

Para um único número

intphi(intn) {
intans=1;
for(inti=0; i<np&&p[i]*p[i] <= n; ++i) {
if(n % p[i] ==0) {
ans *= p[i] -1;
for(n /= p[i]; n % p[i] ==0; n /= p[i])
ans *= p[i];
}
}
if(n>1) ans *= n-1;
returnans;
}

Para um intervalo

intphi[MAX];
voidbuild_phi() {
for(inti=1; i<MAX; ++i)
phi[i] =i;
for(inti=2; i<MAX; ++i)
if(phi[i] ==i) {
phi[i] =i-1;
for(intj=2*i; j<MAX; j+=i)
phi[j] = (phi[j] / i) * (i-1);
}
}

Exponenciação de Matrizes

Miller-Rabin + Pollard's Rho

https://uva.onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=1333

llrandll() {
llt=rand();
return (t << 31) | rand();
}
llmdc(lla, llb) {
returnb ? mdc(b, a % b) : a;
}
llsum(lla, llb, llm) {
a+=b;
if(a>m) a-=m;
returna;
}
llmul(lla, llb, llm) {
llans=0;
while (b) {
if (b&1) ans=sum(ans, a, m);
a=sum(a, a, m);
b >>= 1;
}
returnans;
}
llexp(lla, llb, llm) {
llans=1;
while (b) {
if (b&1) ans=mul(ans, a, m);
a=mul(a, a, m);
b >>= 1;
}
returnans;
}
// Miller-RabinboolisPrime(lln) {
// testes suficientes para garantir corretude para n <= 10^18staticvector<int>a= {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37};
if (n <= 1) return false;
if (n <= 3) return true;
lls=0, d=n-1;
while(d % 2==0)
++s, d >>= 1;
for(inti=0; i<a.size() &&a[i] <n; ++i) {
llx=exp(a[i], d, n);
if(x==1||x==n-1)
continue;
for(intr=1; r<s; ++r) {
x=mul(x, x, n);
if(x==1) return false;
if(x==n-1) break;
}
if(x!=n-1) return false;
}
return true;
}
// usar em numeros imparesllpollardRho(lln) {
llx= (randll() % (n-1)) +1;
llc= (randll() % (n-1)) +1;
lly=x, d=1;
while (d==1) {
x=sum(mul(x, x, n), c, n);
y=sum(mul(y, y, n), c, n);
y=sum(mul(y, y, n), c, n);
d=mdc(abs(x-y), n);
if(d==n) returnpollardRho(n);
}
returnd;
}
// adiciona os fatores primos de n em ans (fora de ordem)voidfactors(lln, vector<ll>&ans) {
if(n <= 1) return;
if(isPrime(n))
ans.push_back(n);
else {
llf= (n % 2==0 ? 2 : pollardRho(n));
factors(f, ans);
factors(n / f, ans);
}
}

Geometria Computacional

Interseção de Retas

https://uva.onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=314

#defineEPS 1e-9
#definesame(x, y) (fabs(x - y) < EPS)
#defineinRange(a, b, c) (c >= fmin(a, b) - EPS && c <= fmax(a, b) + EPS)
structPoint {
doublex, y;
Point(doublex=0, doubley=0): x(x), y(y) {}
};
structLine { doublea, b, c; };
LinepointsToLine(Pointp1, Pointp2) {
Linel;
if (same(p1.x, p2.x)) {
l.a=1.0;
l.b=0.0;
l.c=-p1.x;
} else {
l.a=-(p1.y-p2.y) / (p1.x-p2.x);
l.b=1.0;
l.c=-(l.a*p1.x) -p1.y;
}
returnl;
}
boolparallel(Linel1, Linel2) {
returnsame(l1.a, l2.a) &&same(l1.b, l2.b);
}
boolsameLine(Linel1, Linel2) {
returnparallel(l1, l2) &&same(l1.c, l2.c);
}
boolintersect(Linel1, Linel2) {
return !parallel(l1, l2);
}
PointpointIntersection(Linel1, Linel2) {
Pointp;
p.x= (l2.b*l1.c-l1.b*l2.c) / (l2.a*l1.b-l1.a*l2.b);
if (same(l1.b, 0))
p.y=-(l2.a*p.x+l2.c);
elsep.y=-(l1.a*p.x+l1.c);
returnp;
}

Outras Operações com Ponto e Reta

//Distancia entre os pontos a e bdoubledist(Pointa, Pointb) {
returnhypot(fabs(b.x-a.x), fabs(b.y-a.y));
}
//Retorna a distancia de p para a reta que contem abdoubledistToLine(Pointa, Pointb, Pointp) {
Vecap=toVec(a, p), ab=toVec(a, b);
doubleu=dot(ap, ab) / norm_sq(ab);
a=translate(a, scale(ab, u));
returndist(p, a);
}
doubletoRad(doublet) { returnt*M_PI / 180.0; }
doubletoDeg(doublet) { returnt*180.0 / M_PI; }
// Rotaciona p em theta graus anti-horarioPointrotate(Pointp, doubletheta) {
doublerad=toRad(theta);
returnPoint(p.x*cos(rad) -p.y*sin(rad),
p.x*sin(rad) +p.y*cos(rad));
}

Operações com Vetores

typedefPointVec;
VectoVec(Pointa, Pointb) { returnVec(b.x-a.x, b.y-a.y); }
//Produto escalardoubledot(Veca, Vecb) { returna.x*b.x+a.y*b.y; }
//Produto vetorialdoublecross(Veca, Vecb) { returna.x*b.y-a.y*b.x; }
Pointtranslate(Pointp, Vecv) { returnPoint(p.x+v.x, p.y+v.y); }
Vecscale(Vecv, doubleu) { returnVec(v.x*u, v.y*u); }
//Norma(modulo) do vetor ao quadradodoublenorm_sq(Vecv) { returnv.x*v.x+v.y*v.y; }
//Orientacao anti-horariaboolccw(Pointa, Pointb, Pointc) {
returncross(toVec(a, b), toVec(a, c)) >0;
}
boolcollinear(Pointa, Pointb, Pointc) {
returnsame(cross(toVec(a, b), toVec(a, c)), 0);
}

Interseção de Segmentos

https://uva.onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=127

structSegment {
Points, e;
doubledist;
Segment(Points, Pointe): s(s), e(e) {
dist=hypot(fabs(e.x-s.x), fabs(e.y-s.y));
}
Segment(doublesx=0, doublesy=0, doubleex=0, doubleey=0) {
*this=Segment(Point(sx, sy), Point(ex, ey));
}
//Retorna true se p esta no segmento//Deve ser usado apos collinearboolcontains(Pointp) {
returninRange(s.x, e.x, p.x) &&inRange(s.y, e.y, p.y);
}
boolintersect(Segmentseg) {
boolo1=ccw(s, e, seg.s);
boolo2=ccw(s, e, seg.e);
boolo3=ccw(seg.s, seg.e, s);
boolo4=ccw(seg.s, seg.e, e);
return (o1!=o2&&o3!=o4) ||
(collinear(s, e, seg.s) &&contains(seg.s)) ||
(collinear(s, e, seg.e) &&contains(seg.e)) ||
(collinear(seg.s, seg.e, s) &&seg.contains(s)) ||
(collinear(seg.s, seg.e, e) &&seg.contains(e));
}
};

Área de Polígono

https://www.math10.com/en/geometry/geogebra/fullscreen.htmlhttps://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=45

doublearea(constvector<Point>&p) {
doublea=0.0;
for (inti=1; i<p.size() -1; ++i)
a+=cross(toVec(p[0], p[i]), toVec(p[0], p[i+1]));
returnfabs(a*0.5);
}

Convex Hull

https://practice.geeksforgeeks.org/problems/convex-hull/0https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=45

Pointp0; //Vertice inicial do convex hull//Ordena pontos no sentido anti-horarioboolcmp(Pointp1, Pointp2) {
doubleori=cross(toVec(p0, p1), toVec(p0, p2));
returnsame(ori, 0) ? dist(p0, p1) <dist(p0, p2):
atan2(p1.y-p0.y, p1.x-p0.x) <atan2(p2.y-p0.y, p2.x-p0.x);
}
//Retorna vetor de pontos do convex hullvector<Point>grahamScan(vector<Point>&p) {
vector<Point>newP;
intiMin=0, n=p.size();
for (inti=1; i<n; ++i)
if (p[i].y<p[iMin].y|| (p[i].y==p[iMin].y&&p[i].x<p[iMin].x))
iMin=i;
swap(p[iMin], p[0]);
p0=p[0];
newP.push_back(p0);
sort(p.begin() +1, p.end(), cmp);
for (inti=1; i<n; ++i) {
while (i<n-1&&same(cross(toVec(p0, p[i]), toVec(p0, p[i+1])), 0))
i++;
newP.push_back(p[i]);
}
vector<Point>poly(newP.size());
if (newP.size() >2) {
for (inti=0; i<3; ++i)
poly[i] =newP[i];
intm=3;
for (inti=3; i<newP.size(); ++i) {
while (cross(toVec(poly[m-2], poly[m-1]), toVec(poly[m-2], newP[i])) <EPS)
--m;
poly[m++] =newP[i];
}
poly.resize(m);
}
returnpoly;
}

Par de Pontos Mais Próximos

https://www.urionlinejudge.com.br/judge/pt/problems/view/1295

typedefpair<Point, Point>ppp;
boolcmpX(Pointp1, Pointp2) { returnp1.x<p2.x; }
boolcmpY(Pointp1, Pointp2) { returnp1.y<p2.y; }
pppclosestStrip(Pointstrip[], intm, doubleminD) {
pppres= {{-INF, -INF}, {INF, INF}};
for (inti=0; i<m-1; ++i)
for (intj=i+1; j<m&&strip[j].y-strip[i].y<minD; ++j)
if (dist(strip[i], strip[j]) <minD) {
minD=dist(strip[i], strip[j]);
res= { strip[i], strip[j] };
}
returnres;
}
pppclosestByBruteForce(Pointvp[], intsz) {
pppres= {{-INF, -INF}, {INF, INF}};
for (inti=0; i<sz-1; ++i)
for (intj=i+1; j<sz; ++j)
if (dist(vp[i], vp[j]) <dist(res.first, res.second))
res= {vp[i], vp[j]};
returnres;
}
pppclosestUtil(Pointpx[], intsz) {
if (sz<4)
returnclosestByBruteForce(px, sz);
intmid= (sz-1) / 2, l=0, r=0;
PointmidP=px[mid];
Pointpxl[sz], pxr[sz];
pppres;
for(inti=0; i<sz; i++) {
if(px[i].x<midP.x|| (px[i].x==midP.x&&r>l))
pxl[l++] =px[i];
elsepxr[r++] =px[i];
}
ppppl=closestUtil(pxl, l);
ppppr=closestUtil(pxr, r);
doubleplDist=dist(pl.first, pl.second);
doubleprDist=dist(pr.first, pr.second);
doubled=fmin(plDist, prDist);
res=plDist<prDist ? pl : pr;
sort(px, px+sz, cmpY);
Pointstrip[sz];
intm=0;
for (inti=0; i<sz; ++i)
if (fabs(px[i].x-midP.x) <d)
strip[m++] =px[i];
pppspDist=closestStrip(strip, m, d);
if (dist(spDist.first, spDist.second) <d)
returnspDist;
returnres;
}
pppclosestPair(vector<Point>&ps, intn) {
Pointpx[n];
for (inti=0; i<n; ++i) px[i] =ps[i];
sort(px, px+n, cmpX);
returnclosestUtil(px, n);
}
doubleminimumDist(vector<Point>&ps) {
if (ps.size() <3) returnINF;
pppclose=closestPair(ps, ps.size());
returndist(close.first, close.second);
}

Ponto Dentro do Polígono

https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=45

//Retorna o angulo aob em radianosdoubleangle(Pointa, Pointo, Pointb) {
returnacos(dot(toVec(o, a), toVec(o, b)) / (dist(o, a) *dist(o, b)));
}
//Nao considera pontos nos vertices//como pontos internosboolinPolygon(vector<Point>&p, Pointpt) {
if (p.size() <3) return false;
doublesum=0;
intj=p.size() -1;
for (inti=0; i<p.size(); ++i) {
doubleang=angle(p[j], pt, p[i]);
if (ccw(pt, p[j], p[i]))
sum+=ang;
elsesum-=ang;
j=i;
}
returnsame(fabs(sum) -2*M_PI, 0);
}