У Mainak есть выпуклый многоугольник $$$\mathcal P$$$ с $$$n$$$ вершинами, пронумерованными как $$$A_1, A_2, \ldots, A_n$$$ против часовой стрелки. Координаты $$$i$$$-й точки $$$A_i$$$ даны как $$$(x_i, y_i)$$$, где $$$x_i$$$ и $$$y_i$$$ являются целыми числами.
Кроме того, известно, что внутренний угол при $$$A_i$$$ является либо прямым углом, либо правильным тупым углом. Формально, известно, что:
- $$$90 ^ \circ \le \angle A_{i - 1}A_{i}A_{i + 1} < 180 ^ \circ$$$, $$$\forall i \in \{1, 2, \ldots, n\}$$$, где мы условно считаем $$$A_0 = A_n$$$ и $$$A_{n + 1} = A_1$$$.
Друг Mainak настаивал на том, чтобы все точки $$$Q$$$ такие, что существует хорда многоугольника $$$\mathcal P$$$, проходящая через $$$Q$$$, длины не больше $$$1$$$, должны быть покрашены в $$$\color{red}{\text{красный}}$$$.
Mainak хочет, чтобы вы нашли площадь цветной области, образованной $$$\color{red}{\text{красными}}$$$ точками.
Формально, определите площадь области $$$\mathcal S = \{Q \in \mathcal{P}$$$ | $$$Q \text{ покрашено в } \color{red}{\text{красный}}\}$$$.
Напомним, что хордой многоугольника называется отрезок между двумя точками, лежащими на границе (т.е. вершинами или точками на сторонах) многоугольника.
Первая строка содержит целое число $$$n$$$ ($$$4 \le n \le 5000$$$) — количество вершин многоугольника $$$\mathcal P$$$.
$$$i$$$-я из следующих $$$n$$$ строк содержит два целых числа $$$x_i$$$ и $$$y_i$$$ ($$$-10^9 \le x_i, y_i \le 10^9$$$) — координаты точки $$$A_i$$$.
Гарантируется, что вершины образуют выпуклый многоугольник и перечислены в порядке против часовой стрелки. Также гарантируется, что все внутренние углы лежат в полуинтервале $$$[90 ^ \circ; 180 ^ \circ)$$$.
Выведите площадь многоугольника, покрашенную в $$$\color{red}{\text{красный}}$$$.
Ваш ответ будет считаться правильным, если его абсолютная или относительная погрешность не превосходит $$$10^{-4}$$$.
Формально, пусть ваш ответ равен $$$a$$$, и ответ жюри равен $$$b$$$. Ваш ответ будет принят тогда и только тогда, когда $$$\frac{|a - b|}{\max{(1, |b|)}} \le 10^{-4}$$$.
4 4 5 4 1 7 1 7 5
1.17809724510
5 -3 3 3 1 4 2 -1 9 -2 9
1.07823651333
В первом примере многоугольник $$$\mathcal P$$$ можно представить на декартовой плоскости как:
