QOJ.ac

QOJ

Time Limit: 1 s Memory Limit: 2048 MB Total points: 100

#7667. 起重機平衡

Statistics

凡是有大型建築工程的地方,都會有負責吊運的起重機。人們很少想到,起重機是多麼出色的工程傑作:一個重量(相對)很小的結構,卻能吊起重得多的負載。不過,即使是製造得最好的起重機,能吊起的重量也可能有上限。

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.