Non-Intersecting Segments on the Convex Hull

Given n points in the plane that are not all collinear, consider the set \(S\) of line segments formed by connecting every pair of points. Two segments \(\overline{AB}\) and \(\overline{CD}\) are said to intersect if they share a point that is not one of the endpoints \(A\), \(B\), \(C\), \(D\).

It can be shown that a segment from \(S\) will never intersect any other segment (except at endpoints) if and only if it lies on the boundary of the convex hull of the set of points. Thus, the problem reduces to finding the number of points on the convex hull of the given set (which is equal to the number of boundary segments).

Input: The first line contains an integer n (the number of points). The next n lines each contain two numbers representing the coordinates of a point. It is guaranteed that the points are not all collinear.

Output: Output a single integer denoting the number of segments in \(S\) that do not intersect any other segment, i.e. the number of edges on the convex hull.

Note: Any formulas are provided in \(\LaTeX\) format.

inputFormat

Input begins with an integer n denoting the number of points. Each of the next n lines contains two numbers (which can be integers or floating point numbers) representing the x and y coordinates of a point.

outputFormat

Output a single integer representing the number of non-intersecting segments, which is equal to the number of edges on the convex hull.

sample

3
0 0
1 0
0 1

3