We call a function f from 
to 
affine if it maps straight lines to straight lines. Formally, f is affine if and only if 
for all 
and 
. (Note that this is a weaker condition than linearity: f(x1, x2) = 3·x1 + 2·x2 + 1 is affine but not linear.)
You are given a polygon P in the plane. Determine the smallest integer m ≥ 0 such that there is an affine function f that maps the m-hypercube [0, 1]m to P, or determine that no such m exists.
The first line of the input contains the integer N (1 ≤ N ≤ 100'000), the number of given boundary points of the polygon. The i-th of the next N lines contains two integers Xi and Yi ( - 108 ≤ Xi, Yi ≤ 108), the coordinates of the i-th given boundary point of the polygon.
The counterclockwise boundary of the polygon P is obtained by connecting the given points by line segments. (Xi, Yi) is connected to (Xi + 1, Yi + 1) for 1 ≤ i < N, and (XN, YN) is connected to (X1, Y1). All given points are distinct and the boundary of the polygon P neither intersects nor touches itself.
Print INFINITY, if there is no m such that P is an affine image of the m-hypercube. Otherwise, print a single non-negative integer, the smallest m such that P is an affine image of the m-hypercube.
4
0 0
1 0
1 1
0 1
2
6
0 0
2 0
3 1
3 3
1 3
0 2
3
2
-100000000 29611633
100000000 29611633
1
| ACM-ICPC-Swiss-Subregional 2017 |
|---|
| Finished |
