Minimum Covering Circle Area

Professor Pang studies the minimum covering circle problem and in one of his iterations he has to solve the following sub‐problem. Given a real number \(r\) (the radius) and a convex hull \(C\), define the set

\(S = \{ p \mid \text{the circle with center }p\text{ and radius }r\text{ covers } C \}\)

Determine the area of \(S\). In other words, compute the area of the intersection of all disks of radius \(r\) with centers at the vertices of \(C\) (note that since \(C\) is convex, it is sufficient to consider its vertices).

The input guarantees that \(r\) is greater than or equal to the minimum covering (enclosing) circle radius of \(C\) so that \(S\) is non‐empty. A common approach is to note that \(S\) is convex, and if one can find a point \(O\) in \(S\) (for example, the center of the minimum enclosing circle of \(C\)), then every point \(p\in S\) can be uniquely represented in polar coordinates \(p=O+t\cdot(\cos\theta,\sin\theta)\) (with \(t\ge0\)). The area of \(S\) is given by:

[ \text{Area}(S)=\frac{1}{2}\int_{0}^{2\pi}t(\theta)^2,d\theta. ]

Your task is to compute this area using an appropriate numerical integration (for instance, Simpson's rule), after computing the center \(O\) of the minimum enclosing circle of \(C\). All formulas must be written in LaTeX format.

inputFormat

The first line contains a real number \(r\) and an integer \(n\), where \(r\) is the radius of the circles and \(n\) is the number of vertices of the convex hull \(C\). Each of the following \(n\) lines contains two real numbers, representing the coordinates of a vertex of \(C\) in counterclockwise order.

outputFormat

Output a single real number, the area of \(S = \{p \mid \text{the circle with center }p\text{ and radius }r\text{ covers } C\}\). The answer is accepted if it has an absolute or relative error within \(10^{-6}\).

sample

5 1
0 0

78.5398163397