### Convex hull trick and Li Chao tree

2021

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

### Convex Hull construction using Graham’s Scan

2021

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

### Lattice points inside non-lattice polygon

2021

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

### Pick’s Theorem – area of lattice polygons

2021

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

2021

### Finding the equation of a line for a segment

2021

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

### Basic Geometry

2021

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

### Integration by Simpson’s formula

2021

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

### Newton’s method for finding roots

2021

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

### Ternary Search

2021

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