Minimum Alloy Raw Materials Selection

A company produces an alloy composed of iron, aluminum, and tin. Their process is very simple. They start by importing various raw materials; each raw material is an iron‐aluminum‐tin alloy with a fixed composition. Then, they take a certain amount of each raw material, melt and mix them to produce a new alloy with the desired composition specified by the customer.

Now, the customer provides n alloys, each with required ratios of iron, aluminum, and tin. The company wishes to purchase the minimum number of types of raw materials such that all the customer’s alloy compositions can be obtained by mixing these raw materials.

Mathematically, suppose each alloy composition is represented by a triple \((x, y, z)\) with \(x+y+z=1\). Since these ratios lie on a two‐dimensional simplex, by Carathéodory's theorem, any point inside the convex hull of a set of points in \(\mathbb{R}^2\) can be represented as a convex combination of at most 3 points. In fact, if all customer alloy compositions are the same, only 1 raw material is needed; if all the points lie on a line (i.e. they are collinear), 2 are sufficient; otherwise, 3 raw materials are necessary.

Your task is to determine the minimal number of raw material types required.

inputFormat

The first line contains an integer n (\(1 \le n \le 10^5\)), the number of customer-required alloys.

Each of the following n lines contains three floating-point numbers Fe, Al, Tn representing the proportions of iron, aluminum, and tin respectively. It is guaranteed that for each alloy, \(Fe + Al + Tn = 1\).

outputFormat

Output a single integer representing the minimum number of raw material types required.

sample

1
0.3 0.4 0.3

1