Convex Hull Extension

문제

Dr. Hugh Klidd is a geometry expert who has recently become preoccupied with convex hulls. Recall that for a set of points in the $x\text{-}yx\backslash textrm\{-\}y$ plane, the convex hull is the smallest convex polygon containing all of those points. (A convex polygon has the property that for any two points on/in the polygon, the line segment connecting those two points lies entirely on/in the polygon.) Dr. Klidd has just computed the convex hull of a set of $\text{points,}S,\backslash textrm\{points,\}\; S,$ which he denotes $H(S),H(S),$ and is quite pleased with the result:

• the convex hull has $n\ge 3n\; \backslash geq\; 3$ vertices
• each vertex has integer coordinates
• no three of the convex hull vertices are collinear, i.e., lie on the same line

Dr. Klidd is ambitious, though, so he wants this convex hull to grow. Specifically, he is looking for an extension point, which is a point $p=(x,y)p=(x,y)$ satisfying the following conditions:

1. $xx$ and $yy$ are integers
2. if $S^{\mathrm{\prime }}=S\cup \{p\}S\text{'}\; =\; S\; \backslash cup\; \backslash \{\; p\; \backslash \}$ ($SS$ with $pp$ added), then the convex hull of $S^{\mathrm{\prime }},S\text{'},$ i.e., $H(S^{\mathrm{\prime }}),H(S\text{'}),$ has $n+1n+1$ vertices
3. no three of these $n+1n+1$ vertices are collinear

In other words, an extension point increases the number of convex hull vertices $\text{by}1,\backslash textrm\{by\}\; 1,$ while still keeping all its nice properties. For most convex hulls, $H(S),H(S),$ Dr. Klidd can usually find at least one extension point, but he would like to know how many extension points there are to choose from. He postulates that there is an efficient way to count the number of extension points, but having never taken an algorithms course, he turns to you for help.¹

Figure C.1: Illustration of an extension point for Sample Input 1

---

¹Dr. Klidd has postulated exactly four things before now, so this is his fifth postulate.

입력

The first line of input contains an integer, $n,n,$ the number of vertices of the convex hull that Dr. Klidd starts with $(3\le n\le 50)\mathrm{.}(3\; \backslash leq\; n\; \backslash leq\; 50).$ This is followed by $nn$ lines, each of which contains two space-separated integers, the $xx$ and $yy$ coordinates of one of the $nn$ vertices $(-1000\le x,y\le 1000)\mathrm{.}(-1\backslash ,000\; \backslash leq\; x,y\; \backslash leq\; 1\backslash ,000).$ The $nn$ points are distinct, no three are collinear, and they are given in counterclockwise order.

출력

If the number of extension points for the convex hull specified in the input is infinite, output "infinitely many". Otherwise, output the number of extension points.

5
0 2
-2 0
-1 -3
1 -3
2 1

23

4
-7 -7
7 -7
7 7
-7 7

infinitely many