Humanity's Last Code Exam / 2014_C / Crane Balancing

## Problem Description

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 C.1 shows a cross section of the crane in the first sample input. Assume that every 1×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. Write a program that determines the weight range for which the crane will not topple to the left or to the right.

## Input

The input consists of a single test case. The test case starts with a single integer n (3≤n≤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) (−2000≤x_(i)≤2000,0≤y_(i)≤2000) 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.

## Output

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,∞), display ⌊a⌋..inf. If the crane cannot carry any weight, display `unstable` instead.

## Sample Input 1

## Problem Description

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 C.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. Write a program that determines the weight range for which the crane will not topple to the left or to the right.

## Input

The input consists of a single test case. The test case starts with a single integer \(n\) \((3 \leq n \leq 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\) \((-2000 \leq x_i \leq 2000, 0 \leq y_i \leq 2000)\) 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.

## Output

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 .. \text{inf}\). If the crane cannot carry any weight, display `unstable` instead.

## Sample Input 1