}

(here $\binom{n}{k}$ denotes the usual binomial coefficient, i.e. number of ways to select $k$ objects from set of $n$ objects).

Consider the following problem: you are given a convex polygon with integer vertices and a lot of queries.

Each query is a point, for which we should determine whether it lies inside or on the boundary of the polygon or not.

Suppose the polygon is ordered counter-clockwise. We will answer each query in $O(\log n)$ online.

Let's pick the point with the smallest x-coordinate. If there are several of them, we pick the one with the smallest y-coordinate. Let's denote it as $p_0$.

Now all other points $p_1,\dots,p_n$ of the polygon are ordered by their polar angle from the chosen point (because the polygon is ordered counter-clockwise).

If $p$ is outside, then the sum of those three triangle will be bigger than the size of the triangle.

If it is inside, then it will be equal.

The function `prepair` will make sure that the lexicographical smallest point (smallest x value, and in ties smallest y value) will be $p_0$, and computes the vectors $p_i - p_0$.

Afterwards the function `pointInConvexPolygon` computes the result of a query.

}

}

The **assignment problem** has two equivalent statements:

Here we will consider the solution of the problem based on the algorithm for finding the [minimum cost flow (min-cost-flow)](./graph/min_cost_flow.html), solving the assignment problem in $\mathcal{O}(N^5)$.

Let's build a bipartite network: there is a source $S$, a drain $T$, in the first part there are $N$ vertices (corresponding to rows of the matrix, or orders), in the second there are also $N$ vertices (corresponding to the columns of the matrix, or machines). Between each vertex $i$ of the first set and each vertex $j$ of the second set, we draw an edge with bandwidth 1 and cost $A_{ij}$. From the source $S$ we draw edges to all vertices $i$ of the first set with bandwidth 1 and cost 0. We draw an edge with bandwidth 1 and cost 0 from each vertex of the second set $j$ to the drain $T$.

We find in the resulting network the maximum flow of the minimum cost. Obviously, the value of the flow will be $N$. Further, for each vertex $i$ of the first segment there is exactly one vertex $j$ of the second segment, such that the flow $F_{ij}$ = 1. Finally, this is a one-to-one correspondence between the vertices of the first segment and the vertices of the second part, which is the solution to the problem (since the found flow has a minimal cost, then the sum of the costs of the selected edges will be the lowest possible, which is the optimality criterion).

The complexity of this solution of the assignment problem depends on the algorithm by which the search for the maximum flow of the minimum cost is performed. The complexity will be $\mathcal{O}(N^5)$ using [Dijkstra](./graph/dijkstra.html) or $\mathcal{O}(N^6)$ using [Bellman-Ford](./graph/bellman_ford.html).

The implementation given here is long, it can probably be significantly reduced.

It uses the [D´Esopo-Pape algorithm](./graph/desopo_pape.html) for finding shortest paths.

**The rank of a matrix** is the largest number of linearly independent rows/columns of the matrix. The rank is not only defined for square matrices.

Let the matrix be rectangular and have size $N \times M$.

Note that if the matrix is square and its determinant is non-zero, then the rank is $N$ ($=M$); otherwise it will be less. Generally, the rank of a matrix does not exceed $\min (N, M)$.

You can search for the rank using [Gaussian elimination](./linear_algebra/linear-system-gauss.html). We will perform the same operations as when solving the system or finding its determinant. But if at any step in the $i$-th column there are no rows with an non-empty entry among those that we didn't selected already, then we skip this step and decrease the rank by one (initially the rank is set equal to $\max (N, M)$).

Otherwise, if we have found a row with a non-zero element in the $i$-th column during the $i$-th step, then we mark this row as a selected one and perform the usual operations of taking this row away from the rest.

This algorithm runs in $\mathcal{O}(n^3)$.

const double EPS = 1E-9;

We are going to calculate the value of a definite integral

The solution described here was published in one of the dissertations of **Thomas Simpson** in 1743.

Let $n$ be some natural number. We divide the integration segment $[a; b]$ into $2n$ equal parts:

The error in approximating an integral by Simpson's formula is

The error is asymptotically proportional to $(b-a)^5$. However, the above derivations suggest an error proportional to $(b-a)^4$. Simpson's rule gains an extra order because the points at which the integrand is evaluated are distributed symmetrically in the interval $[a, b]$.

Here $f(x)$ is some user function.

Given an array __A__ of size __N__ and a number __K__. The challenge is to find __K__-th largest number in the array, i.e., __K__-th order statistic.

The basic idea - to use the idea of quick sort algorithm. Actually, the algorithm is simple, it is more difficult to prove that it runs in an average of O(N), in contrast to the quick sort.

template <class T>

As a data structure it is widely used in areas such as data compression, bioinformatics and, in general, in any area that deals with strings and string matching problems.

This is the most naive approach.

Get all the suffixes and sort them using quicksort or mergesort and simultaneously retain their original indices.

Sorting uses $O(n \log n)$ comparisons, and since comparing two strings will additionally take $O(n)$ time, we get the final complexity of $O(n^2 \log n)$.

Strictly speaking the following algorithm will not sort the suffixes, but rather the cyclic shifts of a string.

However we can very easily derive an algorithm for sorting suffixes from it: