### Convex hull trick and Li Chao tree

1. Overview Consider the following problem. There are $n$ cities. You want to travel from city $1$ to city $n$ by car. To do this […]

1. Overview Consider the following problem. There are $n$ cities. You want to travel from city $1$ to city $n$ by car. To do this […]

In this article we will discuss the problem of constructing a convex hull from a set of points. Consider $N$ points given on a plane, […]

1. Overview For lattice polygons there is Pick’s formula to enumerate the lattice points inside the polygon. What about polygons with arbitrary vertices? Let’s process […]

A polygon without self-intersections is called lattice if all its vertices have integer coordinates in some 2D grid. Pick’s theorem provides a way to compute […]

1. Definition Consider two sets $A$ and $B$ of points on a plane. Minkowski sum $A + B$ is defined as $\{a + b| a […]

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 […]

Let a simple polygon (i.e. without self intersection, not necessarily convex) be given. It is required to calculate its area given its vertices. 1. Method […]

Given three points $p_1$, $p_2$ and $p_3$, calculate an oriented (signed) area of a triangle formed by them. The sign of the area is determined […]

Given $n$ segments on a line, each described by a pair of coordinates $(a_{i1}, a_{i2})$. We have to find the length of their union. The […]

Given two circles. It is required to find all their common tangents, i.e. all such lines that touch both circles simultaneously. The described algorithm will […]

You are given two circles on a 2D plane, each one described as coordinates of its center and its radius. Find the points of their […]

Given the coordinates of the center of a circle and its radius, and the equation of a line, you’re required to find the points of […]

You are given two segments AB and CD, described as pairs of their endpoints. Each segment can be a single point if its endpoints are […]

You are given two segments $(a, b)$ and $(c, d)$. You have to check if they intersect. Of course, you may find their intersection and […]

You are given two lines, described via the equations $a_1 x + b_1 y + c_1 = 0$ and $a_2 x + b_2 y + […]

The task is: given the coordinates of the ends of a segment, construct a line passing through it. We assume that the segment is non-degenerate, […]

In this article we will consider basic operations on points in Euclidean space which maintains the foundation of the whole analytical geometry. We will consider […]

We are going to calculate the value of a definite integral $$\int_a ^ b f (x) dx$$ The solution described here was published in one […]

This is an iterative method invented by Isaac Newton around 1664. However, this method is also sometimes called the Raphson method, since Raphson invented the […]

We are given a function $f(x)$ which is unimodal on an interval $[l, r]$. By unimodal function, we mean one of two behaviors of the […]