Crane Stability

A crane cross‐section is modeled as a polygon resting on the x–axis. Every 1×1 unit of area weighs 1 kilogram. An extra load is attached at one of the polygon’s vertices. The crane will not topple if the combined center of mass of the polygon and the extra weight lies between the leftmost and rightmost contact points with the ground. These contact points are the vertices (or points on edges) which lie on the x–axis.

Let the polygon have an (absolute) area A and a center–of–mass x–coordinate \(x_c\) (computed using the standard formulas). Suppose the extra weight of \(W\) kg is attached at a vertex whose x–coordinate is \(x_0\). Then the overall center–of–mass is given by

[ X = \frac{A, x_c + W, x_0}{A+W}. ]

If the crane touches the ground at points with x–coordinates \(L\) and \(R\) (with \(L< R\)), the crane remains stable provided that

[ L \le X \le R. \qquad (\text{i.e. } L \le \frac{A, x_c + W, x_0}{A+W} \le R ) ]

Your job is to determine the range of extra weight \(W\) for which the crane will not topple. If the range is unbounded above (or below), output inf for that bound. If no extra weight will ever make the crane stable, output unstable.

Note. It is guaranteed that the polygon rests on the x–axis (i.e. at least two vertices lie on it) and that its weight per unit area is 1 kilogram.

inputFormat

The first line contains an integer \(n\) (\(3 \le n \le 10^5\)), the number of vertices of the polygon in order (either clockwise or counterclockwise). Each of the next \(n\) lines contains two real numbers \(x\) and \(y\) (\(|x|,|y| \le 10^4\)), the coordinates of a vertex. It is guaranteed that at least two vertices have \(y=0\) (the contact points with the ground).

The last line contains an integer \(k\) (1 \(\le k \le n\)), which specifies that the extra load is attached at the \(k\)–th vertex (the vertices are 1–indexed).

outputFormat

If there is no extra weight that will keep the crane stable, output a single line with the word unstable. Otherwise, output two tokens: the minimum extra weight \(W_{min}\) and the maximum extra weight \(W_{max}\) for which the crane remains stable. For any unbounded limit, output inf instead of a number. Output real numbers using 8 decimal places. (It is guaranteed that if a solution exists, \(W_{min}\) and \(W_{max}\) can be determined uniquely.)

How to determine the range:

• Compute the area \(A\) and the center–of–mass \(x_c\) of the polygon using the standard formulas: \[ A = \frac{1}{2} \left|\sum_{i=0}^{n-1} (x_i y_{i+1} - x_{i+1} y_i)\right|,\qquad x_c = \frac{1}{6A}\sum_{i=0}^{n-1}(x_i + x_{i+1})(x_i y_{i+1}-x_{i+1} y_i). \]
• Let \(L\) be the minimum \(x\) among all vertices with \(y=0\) and \(R\) be the maximum.
• The combined center–of–mass when extra weight \(W\) is attached at \(x_0\) (the x–coordinate of the \(k\)–th vertex) is \[ X = \frac{A\, x_c + W\, x_0}{A+W}. \]
• The crane is stable when \(L \le X \le R\). Since \(X\) is a monotonic function of \(W\) (increasing if \(x_0 > x_c\) and decreasing if \(x_0 < x_c\)), the condition yields a contiguous range \([W_{min},W_{max}]\) (where one of the endpoints may be unbounded, in which case output inf). If no \(W \ge 0\) can satisfy the inequality, output unstable.

Implementation note: Use double–precision arithmetic and output real numbers with 8 decimal places.

sample

5
0 0
2 0
2 2
1 3
0 2
4

0.00000000 inf