[Solution] Mainak and the Bleeding Polygon Codeforces Solution

H. Mainak and the Bleeding Polygon

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

Mainak has a convex polygon $\mathcal{P}$ with 𝑛$n$ vertices labelled as 𝐴1,𝐴2,…,𝐴𝑛$A_1,A_2,\dots ,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∘≤∠𝐴𝑖−1𝐴𝑖𝐴𝑖+1<180∘${90}^{\circ }\le \mathrm{\angle }{A}_{i-1}{A}_i{A}_{i+1}<{180}^{\circ }$, ∀𝑖∈{1,2,…,𝑛}$\mathrm{\forall }i\in \{1,2,\dots ,n\}$ where we conventionally consider 𝐴0=𝐴𝑛$A_0=A_n$ and 𝐴𝑛+1=𝐴1$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$1$, must be coloured red$\text{red}$.

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

Formally, determine the area of the region ={𝑄∈$\mathcal{S}=\{Q\in \mathcal{P}$ | 𝑄 is coloured red}$Q\text{ is coloured }\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

The first line contains an integer 𝑛$n$ (4≤𝑛≤5000$4\le n\le 5000$) — the number of vertices of a polygon $\mathcal{P}$.

Solution Click Below:-  👉CLICK HERE👈

👇👇👇👇👇

The 𝑖$i$-th line of the next 𝑛$n$ lines contain two integers 𝑥𝑖$x_i$ and 𝑦𝑖$y_i$ (−109≤𝑥𝑖,𝑦𝑖≤109$-{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∘;180∘)$[{90}^{\circ };{180}^{\circ })$.

Output

Print the area of the region coloured in red$\text{red}$.

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

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