Məsələlər
Выпуклые оболочки
Выпуклые оболочки
Выпуклая оболочка множества точек плоскости - наименьший выпуклый многоугольник, содержащий эти точки.
Вам дано \textbf{n} точек на плоскости. Произвольно одна из них выбирается и удаляется.
\includegraphics{https://static.e-olymp.com/content/49/49270e28ebc371c9e6e548fe5edf6353526f0ecb.jpg}
Найти среднее число вершин выпуклой оболочки результирующего множества. В этой задаче считайте, что если выпуклая оболочка - отрезок, то в ней две вершины. Если же она - невырожденный многоугольник, то все углы при вершинах строго меньше .
\InputFile
В первой строке содержится единственное число \textbf{n} (\textbf{3} ≤ \textbf{n} ≤ \textbf{200000}) - количество точек во множестве. В последующих \textbf{n} строках заданы пары чисел, не превышающих по модулю \textbf{10^9} - координаты точек. Никакие две точки не совпадают.
\OutputFile
Выведите среднее число вершин в выпуклой оболочке множества без одной точки в виде несократимой дроби \textbf{p/q}.
Giriş verilənləri #1
5 0 0 0 4 4 0 3 3 4 4
Çıxış verilənləri #1
17/5