У 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{красный}}\}\).
Напомним, что хордой многоугольника называется отрезок между двумя точками, лежащими на границе (т.е. вершинами или точками на сторонах) многоугольника.
Выходные данные
Выведите площадь многоугольника, покрашенную в \(\color{red}{\text{красный}}\).
Ваш ответ будет считаться правильным, если его абсолютная или относительная погрешность не превосходит \(10^{-4}\).
Формально, пусть ваш ответ равен \(a\), и ответ жюри равен \(b\). Ваш ответ будет принят тогда и только тогда, когда \(\frac{|a - b|}{\max{(1, |b|)}} \le 10^{-4}\).