competitve_programming_library

Author: Nguyen Anh Tuan (gsdt) MIT License

Math

Modulo

Matrix

Supported: add, subtract, multiply, power
Operator () overloaded, ex: M(1,2) = 12

Geomatrix

Point

Get distance to another point

Circle

Create new circle from three points
Get center and radius

Gaussian Elimitation

There are two version:

Usage:

Contructor: input an matrix to solve.
solve(): Solve equation

FFT - multiplying two polynomials

Data structure

Fenwick Tree

add(pos, value): add some value to position pos.
set(pos, value): set a value to position pos.
sumToPosition(pos): get sum from first position to pos.
sumOfRage(start_pos, end_pos): get sum from start_pos to end_pos.
operator []: for get data, not for set data.
clear(): remove all data from tree.
size(): get number of element in tree.

Disjoin Set Union (updated: 09:22AM 18/05/2019)

unionSets(a, b): join two set has element a and b.
findSet(a): find root of set a.
isSameSet(a, b): test if set a and set b is same.
getSetSize(a): number of element in set a.

Sum-SegmentTree

SegmentTree(n): create segment tree to manage n element.
update(l, r, v): increasing value from l to r by value v.
query(l,r): query sum from l to r.

Graph

Adjacency List Graph

AdjacencyListGraph(n): create graph with n+1 vertex: from 0 to n.
addDirectedEdge(startVertex, endVertex, weight = 1): add an weighted directed edge.
addUndirectedEdge(firstVertex, secondVertex, weight = 1): add an weighted undirected edge.
showGraph(): show current graph.
shortest(startVertex, endVertext): using Dijkstra alogrithm find shortest path between to vertex. Return shorted path and direction. This implementation passed SPOJ