Mainak and the Bleeding Polygon
Contest: Codeforces Round 819 (Div. 1 + Div. 2) and Grimoire of Code Annual Contest 2022
Difficulty rating: 3500
Tags: binary search, geometry, implementation, math

Mainak has a convex polygon $$$\mathcal P$$$ with $$$n$$$ vertices labelled as $$$A_1, A_2, \ldots, A_n$$$ in a counter-clockwise fashion. The coordinates of the $$$i$$$-th point $$$A_i$$$ are given by $$$(x_i, y_i)$$$, where $$$x_i$$$ and $$$y_i$$$ are both integers.

Further, it is known that the interior angle at $$$A_i$$$ is either a right angle or a proper obtuse angle. Formally it is known that:

- $$$90 ^ \circ \le \angle A_{i - 1}A_{i}A_{i + 1} < 180 ^ \circ$$$, $$$\forall i \in \{1, 2, \ldots, n\}$$$ where we conventionally consider $$$A_0 = A_n$$$ and $$$A_{n + 1} = A_1$$$.

Mainak's friend insisted that all points $$$Q$$$ such that there exists a chord of the polygon $$$\mathcal P$$$ passing through $$$Q$$$ with length not exceeding $$$1$$$, must be coloured $$$\color{red}{\text{red}}$$$.

Mainak wants you to find the area of the coloured region formed by the $$$\color{red}{\text{red}}$$$ points.

Formally, determine the area of the region $$$\mathcal S = \{Q \in \mathcal{P}$$$ | $$$Q \text{ is coloured } \color{red}{\text{red}}\}$$$.

Recall that a chord of a polygon is a line segment between two points lying on the boundary (i.e. vertices or points on edges) of the polygon.

Input format:
The first line contains an integer $$$n$$$ ($$$4 \le n \le 5000$$$) — the number of vertices of a polygon $$$\mathcal P$$$.

The $$$i$$$-th line of the next $$$n$$$ lines contain two integers $$$x_i$$$ and $$$y_i$$$ ($$$-10^9 \le x_i, y_i \le 10^9$$$) — the coordinates of $$$A_i$$$.

Additional constraint on the input: The vertices form a convex polygon and are listed in counter-clockwise order. It is also guaranteed that all interior angles are in the range $$$[90^\circ ; 180^\circ )$$$.

Output format:
Print the area of the region coloured in $$$\color{red}{\text{red}}$$$.

Your answer is considered correct if its absolute or relative error does not exceed $$$10^{-4}$$$.

Formally, let your answer be $$$a$$$, and the jury's answer be $$$b$$$. Your answer is accepted if and only if $$$\frac{|a - b|}{\max{(1, |b|)}} \le 10^{-4}$$$.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
In the first example, the polygon $$$\mathcal P$$$ can be visualised on the Cartesian Plane as:

Example input:
4
4 5
4 1
7 1
7 5

Example output:
1.17809724510

Example input:
5
-3 3
3 1
4 2
-1 9
-2 9

Example output:
1.07823651333

Editorial:
Clearly, the unsafe area is bounded by the envelope of the curve you get if you slide a rod of length $$$1$$$ around the interior of the polygon and pressed against the edges at all times.
Observation 1: The length of each side of the polygon is $$$\geq 1$$$.
This one is obvious. Further, it implies that (almost always) we only need to consider unsafe areas formed by adjacent pairs of edges (there is one exception to this which is a rectangle with a side of length $$$1$$$, in which case the whole rectangle is unsafe). The proof is left as an exercise to the reader (our proof required some casework and induction on the angle and number of edges). The unsafe area for the whole polygon is the union of the unsafe areas formed by each pair of adjacent edges.
Two adjacent edges can be viewed as a pair of lines $$$y=0$$$ and $$$y=x \cdot \tan{( \alpha )}$$$ where $$$\alpha$$$ is the angle between the edges (which is $$$\geq \frac{\pi}{2}$$$). As it turns out, the envelope of the unsafe area is given by the parametric equations
$$$$$$\begin{aligned} x&=f(\theta,\alpha)=\frac{\sin\left(\theta-\alpha\right)}{\sin \alpha}+\frac{\cos\left(\theta-\alpha\right)\sin\left(\theta\right)\cos\left(\theta\right)}{\sin \alpha} \\ y&=g(\theta,\alpha)=\frac{\cos\left(\theta-\alpha\right)\sin^{2}\left(\theta\right)}{\sin \alpha} \\ \alpha & < \theta < \pi \end{aligned}$$$$$$
A sketch of the area for $$$\alpha=\frac{2\pi}{3}$$$:
Also, the area is given by the formula
$$$$$$\begin{aligned} \frac{\cot{(\alpha)}+(\pi-\alpha) \cdot (\csc^2{(\alpha)}+2)}{16} \end{aligned}$$$$$$
We can easily just add up these values for each pair of adjacent edges. However, we are overestimating the area. We need to subtract out the intersecting parts of the individual unsafe areas.
Observation 2: At most $$$2$$$ individual unsafe areas cover any given point. If $$$2$$$ unsafe areas intersect, they are the areas made by $$$3$$$ successive edges.
If say, $$$3$$$ unsafe areas covered a point, then one of them must be between non-adjacent edges, which is not possible by the implications of observation 1. Furthermore, if the intersection of the unsafe areas is non-empty, the length of the common edge must be $$$< 2$$$, otherwise it will definitely be empty (this fact should be intuitively obvious). However, since the polygon has vertices has integer coordinates, if the length of an edge is $$$< 2$$$, it must be $$$1$$$ (it is parallel to one axis) or $$$\sqrt{2}$$$ (it is diagonal). Note that each possibility of edges with such lengths in an oriented fashion can occur at most once. Which gives us observation 3.
Observation 3: The number of sides of length $$$< 2$$$ is $$$\leq 8$$$.
What this basically means is that we will have to compute the area of the intersection of two unsafe areas only $$$\mathcal{O}(1)$$$ times.
Coming back to the curve, its area can be given by the integral
$$$$$$\begin{aligned} \int{y(\theta) \cdot \frac{\mathrm{d} x(\theta)}{\mathrm{d}\theta}\text{ }\mathrm{d}\theta}=\frac{1}{\sin^2{\alpha}}\int{[2\cos^2{(\theta-\alpha)}\cos^2{\theta}\sin^2{\theta}-\sin{(\theta-\alpha)}\cos{(\theta-\alpha)}\sin^3{\theta}\cos{\theta}]\text{ }\mathrm{d}\theta} \end{aligned}$$$$$$
This indefinite integral evaluates to
$$$$$$\begin{aligned} \frac{1}{64\sin^2{\alpha}}(\sin{(2 (\alpha - 3 \theta))} - \sin{(2 (\alpha - 2 \theta))} - 4 \sin{(2 (\alpha - \theta))} - \sin{(2 (\alpha + \theta))} - 4 \theta \cos{(2 \alpha)} + 8 \theta - 2 \sin{(4 \theta)}) + C \end{aligned}$$$$$$
Now, all we need to do is find the bounds of integration by finding the point at which the curves cross.
Now, for an edge of length $$$L$$$, where $$$L$$$ is either $$$1$$$ or $$$\sqrt 2$$$, we need to find the area of overlap and subtract it from our overestimated value. if we place the edge on the $$$x$$$-axis starting from origin, then the adjacent edges which were at an angle $$$\alpha_1$$$ and $$$\alpha_2$$$, now are straight lines, one at an angle $$$\alpha_1$$$ passing from the origin, whereas other is another straight line at an angle $$$\pi - \alpha_2$$$ passing through $$$(L, 0)$$$. Clearly, the parametric equations of the two envelopes would be $$$(f(\theta, \alpha_1), g(\theta, \alpha_1))$$$ for $$$\alpha_1 \le \theta \le \pi$$$ and $$$(L - f(\phi, \alpha2), g(\phi, \alpha_2))$$$ for $$$\alpha_2 \le \phi \le \pi$$$.
Observation 4: $$$g(\theta, \alpha)$$$, for a fixed $$$\alpha \in [\frac \pi 2, \pi)$$$, is a decreasing function of $$$\theta$$$, $$$\alpha \le \theta \le \pi$$$.
This fact can be easily verified from the equation of $$$g(\alpha, \theta)$$$ as $$$\cos(x)$$$ is decreasing in the range of $$$(\theta - \alpha)$$$ i.e. $$$[0, \pi - \alpha] \subset [0, \frac \pi 2]$$$, and $$$\sin^2(x)$$$ is decreasing in the range of $$$\theta$$$, i.e. $$$[\alpha, \pi] \subset [\frac \pi 2, \pi]$$$.
This means for a given value, $$$y = \lambda$$$, we can binary search in $$$\mathcal O(\log(\frac 1 \varepsilon))$$$, the value of $$$\theta$$$, such that $$$g(\alpha, \theta) = \lambda$$$. Once we get $$$\theta$$$, we can further get the $$$x$$$-coordinate just by plugging $$$\theta$$$ in $$$f(\theta, \alpha)$$$. Consequently, for both the parametric equations, we can evaluate $$$x$$$ as a function of $$$y$$$, in $$$\mathcal O(\log(\frac 1 \varepsilon))$$$ time.
Observation 5: If the coordinates of the intersection of $$$(f(\theta, \alpha_1), g(\theta, \alpha_1))$$$ for $$$\alpha_1 \le \theta \le \pi$$$ and $$$(L - f(\phi, \alpha2), g(\phi, \alpha_2))$$$ for $$$\alpha_2 \le \phi \le \pi$$$ is $$$(h, k)$$$, then we can can binary search on $$$k$$$ in $$$\mathcal O(\log(\frac 1 \varepsilon))$$$ function evaluations of $$$x$$$ as a function of $$$y$$$.
Observe that $$$0 < k < \sin(\max(\alpha_1, \alpha_2))$$$. Now, for a given guess $$$\lambda$$$ of the $$$y$$$-coordinate of the intersection point, let's say the first parametric function provides an $$$x$$$-coordinate of $$$x_1$$$ and the second parametric curve gives $$$x_2$$$. In other words, $$$(x_1, \lambda)$$$ and $$$(x_2, \lambda)$$$ are points on the first and the second curves respectively. Now, if $$$\lambda > k$$$, then we must have $$$x_1 < x_2$$$, whereas if $$$\lambda < k$$$, we have $$$x_1 > x_2$$$; and thus we can find the value of $$$k$$$ in $$$\mathcal O(log(\frac 1 \varepsilon))$$$ evaluations of $$$x_1$$$ and $$$x_2$$$ using a binary search.
Therefore we can find the intersection point (and therefore the corresponding $$$\theta$$$ and $$$\phi$$$ values) in $$$\mathcal O(\log^2(\frac 1 \varepsilon))$$$ time. Once we have the $$$\theta$$$ and the $$$\phi$$$ values, we get the bounds of the indefinite integral after which we just plug in the values $$$\theta$$$ and $$$\phi$$$ to the indefinite integral to get the overlap area.
Since we are doing this only for edges of length $$$< 2$$$, by observation 3, the final time complexity is $$$\mathcal{O}(n+\log^2{\varepsilon^{-1}})$$$.
However, a solution doing this for every edge would run in $$$\mathcal{O}(n\log^2{\varepsilon^{-1}})$$$ time. For the given constraints, this optimization was not necessary to pass.