19482번 - Unrumpf 스페셜 저지다국어

While preparing a brute-force solution for problem "Rumpf", we have written a program that repeatedly does the following: pick a random number $n_i$ uniformly at random between 10 and 100. Generate $n_i$ random points with integer coordinates, picking each coordinate independently and uniformly at random from all integers between 0 and $10^9$, inclusive. Find the convex hull of those points.

You are given 10000 polygons generated by this program. For each polygon, you need to guess the value $n_i$ that was used for generating it.

The first line of the input file contains the number $k$ of convex hulls to process. $k$ is always equal to 10000. Each of the next $k$ lines describes a convex hull: the number of its vertices $m_i$, followed by $m_i$ pairs of integers --- the coordinates of the vertices. The vertices are given in counterclockwise order, no three consecutive vertices lie on the same line.

It is guaranteed that the convex hulls were generated according to the method described above.

You need to output $k$ lines, each with one integer: your guess for the initial number $n_i$ of random vertices used to generate the corresponding convex hull. This number must be between 10 and 100, inclusive.

Your answer will be accepted if the average (over all 10000 hulls) absolute difference between the natural logarithm of your guess and the natural logarithm of the true $n_i$ is below 0.2.

In the sample case, your answer will be accepted simply if all your guesses are between 10 and 100, inclusive.

You can download the sample input and the values of $n_i$ used in generating it at unrumpf.zip. There are 10 non-sample testcases in this problem.