## GUPTA MECHANICAL

IN THIS WEBSITE I CAN TELL ALL ABOUT TECH. TIPS AND TRICKS APP REVIEWS AND UNBOXINGS ALSO TECH. NEWS .............

# [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 ${A}_{1},{A}_{2},\dots ,{A}_{n}$ in a counter-clockwise fashion. The coordinates of the $i$-th point ${A}_{i}$ are given by $\left({x}_{i},{y}_{i}\right)$, 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 \mathrm{\angle }{A}_{i-1}{A}_{i}{A}_{i+1}<{180}^{\circ }$$\mathrm{\forall }i\in \left\{1,2,\dots ,n\right\}$ 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 $\text{red}$.

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

Formally, determine the area of the region $\mathcal{S}=\left\{Q\in \mathcal{P}$ | .

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\le n\le 5000$) — the number of vertices of a polygon $\mathcal{P}$.

Solution Click Below:-  👉
👇👇👇👇👇

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 $\left[{90}^{\circ };{180}^{\circ }\right)$.

Output

Print the area of the region coloured in $\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\left(1,|b|\right)}\le {10}^{-4}$.