#GYM104757C. Convex Hull Extension
Convex Hull Extension
本题没有可用的提交语言。
Description
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\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 $\textrm{points,}~S,$ which he denotes $H(S),$ and is quite pleased with the result:
- the convex hull has $n \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)$ satisfying the following conditions:
- $x$ and $y$ are integers
- if $S' = S \cup \{ p \}$ ($S$ with $p$ added), then the convex hull of $S',$ i.e., $H(S'),$ has $n+1$ vertices
- no three of these $n+1$ vertices are collinear
The first line of input contains an integer, $n,$ the number of vertices of the convex hull that Dr. Klidd starts with $(3 \leq n \leq 50).$ This is followed by $n$ lines, each of which contains two space-separated integers, the $x$ and $y$ coordinates of one of the $n$ vertices $(-1\,000 \leq x,y \leq 1\,000).$ The $n$ 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.
Input
The first line of input contains an integer, $n,$ the number of vertices of the convex hull that Dr. Klidd starts with $(3 \leq n \leq 50).$ This is followed by $n$ lines, each of which contains two space-separated integers, the $x$ and $y$ coordinates of one of the $n$ vertices $(-1\,000 \leq x,y \leq 1\,000).$ The $n$ points are distinct, no three are collinear, and they are given in counterclockwise order.
Output
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
4
-7 -7
7 -7
7 7
-7 7
23
infinitely many
Note
Dr. Klidd has postulated exactly four things before now, so this is his fifth postulate.