题目描述

Wherever there is large-scale construction, you will find cranes that do the lifting. One hardly ever thinks about what marvelous examples of engineering cranes are: a structure of (relatively) little weight that can lift much heavier loads. But even the best-built cranes may have a limit on how much weight they can lift.

The Association of Crane Manufacturers (ACM) needs a program to compute the range of weights that a crane can lift. Since cranes are symmetric, ACM engineers have decided to consider only a cross section of each crane, which can be viewed as a polygon resting on the $x$-axis.

Figure 1: Crane cross section

Figure 1 shows a cross section of the crane in the first sample input. Assume that every $1 \times 1$ unit of crane cross section weighs 1 kilogram and that the weight to be lifted will be attached at one of the polygon vertices (indicated by the arrow in Figure 1). Write a program that determines the weight range for which the crane will not topple to the left or to the right.

输入格式

The input consists of a single test case. The test case starts with a single integer $n$ ($3 \le n \le 100$), the number of points of the polygon used to describe the crane’s shape. The following $n$ pairs of integers $x_ i, y_ i$ ($-2\, 000 \le x_ i \le 2\, 000, 0 \le y_ i \le 2\, 000$) are the coordinates of the polygon points in order. The weight is attached at the first polygon point and at least two polygon points are lying on the $x$-axis.

输出格式

Display the weight range (in kilograms) that can be attached to the crane without the crane toppling over. If the range is $[a,b]$, display $\lfloor a \rfloor$ .. $\lceil b \rceil$. For example, if the range is $[1.5,13.3]$, display 1 .. 14. If the range is $[a,\infty )$, display $\lfloor a \rfloor$ .. inf. If the crane cannot carry any weight, display unstable instead.

题目大意

无论哪里有大规模的施工，您都会发现起重机可以起重。人们几乎从未想过工程起重机的奇妙例子是什么：一种（相对）重量很小的结构，可以举起更重的负载。但即使是最好的起重机也可能对它们可以举起的重量有限制。

起重机制造商协会（ACM）需要一个程序来计算起重机可以提升的重量范围。由于起重机是对称的，ACM工程师决定只考虑每台起重机的横截面，这可以看作是一个多边形，位于x-轴。

图1显示了第一个样本输入中起重机的横截面。

假设每个1×1单位起重机横截面重1公斤，要提升的重量将附着在其中一个多边形顶点（如图1中的箭头所示）。编写一个程序，确定起重机不会向左或向右倾倒的重量范围。

输入由单个测试用例组成。测试用例以单个整数n开头,用于描述起重机形状的多边形的点数。以下n对整数是按顺序排列的点的坐标。权重附着在第一个多边形点上，并且至少有两个多边形点位于x-轴。

输出格式

显示可在起重机不倒塌的情况下连接到起重机的重量范围（以千克为单位）。如果范围是 [a,b], 显示⌊a⌋ .. ⌈b⌉. 例如，如果范围是[1.5,13.3], 显示 1 ..14. 如果范围是[a,∞), 显示⌊a⌋ .. inf. 如果起重机不能承载任何重量，请显示unstable.

说明/提示

时间限制： 1000 ms， 内存限制： 1048576 kB.

2014年国际大学生编程大赛（ACM-ICPC）世界总决赛

7
50 50
0 50
0 0
30 0
30 30
40 40
50 40

0 .. 1017

7
50 50
0 50
0 0
10 0
10 30
20 40
50 40

unstable

提示

Time limit: 1000 ms, Memory limit: 1048576 kB.

International Collegiate Programming Contest (ACM-ICPC) World Finals 2014