QOJ.ac

QOJ

Limite de temps : 1 s Limite de mémoire : 2048 MB Points totaux : 100

#7667. クレーンの釣り合い

Statistiques

大規模な建設工事が行われる場所には、荷物を持ち上げるクレーンがあります。クレーンがいかに見事な工学の実例であるかを考えることは、ほとんどありません。(比較的)軽い構造物が、それよりはるかに重い荷物を持ち上げるのです。しかし、最もよく作られたクレーンでも、持ち上げられる重量には限界があるかもしれません。

Association of Crane Manufacturers(ACM)は、クレーンが持ち上げられる重量の範囲を計算するプログラムを必要としています。クレーンは対称なので、ACM の技術者たちは、各クレーンの断面だけを考えることにしました。この断面は、$x$ 軸の上に置かれた多角形とみなせます。

problem_7667_bf4fd58132dcf6b3d95a000392fc1429.png

図 C.1:クレーンの断面

図 C.1 は、最初の入力例におけるクレーンの断面を示しています。クレーンの断面の $1 \times 1$ 単位ごとの重量を 1 キログラムとし、持ち上げる重りは多角形の頂点の一つ(図 C.1 の矢印が示す頂点)に取り付けるものとします。クレーンが左右どちらにも倒れない重量の範囲を求めるプログラムを書いてください。

入力

入力は一つのテストケースからなります。最初に、クレーンの形を表す多角形の頂点数を示す整数 $n$($3 \le n \le 100$)が与えられます。続く $n$ 組の整数 $x_i,y_i$($-2\,000 \le x_i \le 2\,000$、$0 \le y_i \le 2\,000$)は、多角形の頂点の座標を順番に表します。重りは最初の頂点に取り付けられ、少なくとも二つの頂点が $x$ 軸上にあります。

出力

クレーンを倒さずに取り付けられる重りの重量範囲を、キログラム単位で出力してください。範囲が $[a,b]$ なら、$\lfloor a\rfloor$ .. $\lceil b\rceil$ と出力します。例えば、範囲が $[1.5,13.3]$ なら 1 .. 14 と出力します。範囲が $[a,\infty)$ なら、$\lfloor a\rfloor$ .. inf と出力します。クレーンがどの重量も支えられない場合は、代わりに unstable と出力してください。

入出力例

入力 1

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

出力 1

0 .. 1017

入力 2

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

出力 2

unstable

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.