eolymp
bolt
Try our new interface for solving problems
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}.
Zaman məhdudiyyəti 2 saniyə
Yaddaşı istafadə məhdudiyyəti 256 MiB
Giriş verilənləri #1
5
0 0
0 4
4 0
3 3
4 4
Çıxış verilənləri #1
17/5