Convex Hulls#4068
The convex hull of a set of points on a plane is the smallest convex polygon that encloses all the points.
You are given points on a plane. One of these points is selected at random and removed.
Your task is to determine the average number of vertices of the convex hull formed by the remaining points. For this problem, consider that if the convex hull is a line segment, it is counted as having two vertices. If it forms a non-degenerate polygon, then all angles at the vertices are strictly less than degrees.
The first line contains a single integer (3 \leq n \leq 200000), representing the number of points in the set. The following lines each contain a pair of integers, with each coordinate not exceeding 10^9 in absolute value, representing the coordinates of the points. No two points are identical.
Print the average number of vertices in the convex hull of the set after removing one point, expressed as an irreducible fraction .
Beispiel 1