QOJ.ac

QOJ

実行時間制限: 1 s メモリ制限: 2048 MB 満点: 100

#7667. Równowaga żurawia

統計

Wszędzie tam, gdzie prowadzi się wielkie prace budowlane, można znaleźć żurawie podnoszące ciężary. Rzadko myśli się o tym, jak wspaniałymi przykładami inżynierii są żurawie: konstrukcja o (stosunkowo) niewielkiej masie potrafi podnosić znacznie cięższe ładunki. Jednak nawet najlepiej zbudowane żurawie mogą mieć ograniczenie masy, jaką potrafią podnieść.

Association of Crane Manufacturers (ACM) potrzebuje programu obliczającego zakres mas, które żuraw może podnosić. Ponieważ żurawie są symetryczne, inżynierowie ACM postanowili rozpatrywać tylko przekrój każdego żurawia, który można traktować jak wielokąt spoczywający na osi $x$.

problem_7667_bf4fd58132dcf6b3d95a000392fc1429.png

Rysunek C.1: Przekrój żurawia

Rysunek C.1 przedstawia przekrój żurawia z pierwszego przykładu. Załóż, że każdy fragment przekroju o wymiarach $1 \times 1$ waży 1 kilogram, a podnoszony ciężar będzie przymocowany do jednego z wierzchołków wielokąta (wskazanego strzałką na rysunku C.1). Napisz program wyznaczający zakres mas, dla których żuraw nie przewróci się ani w lewo, ani w prawo.

Wejście

Wejście zawiera jeden przypadek testowy. Zaczyna się on od jednej liczby całkowitej $n$ ($3 \le n \le 100$), oznaczającej liczbę wierzchołków wielokąta opisującego kształt żurawia. Następne $n$ par liczb całkowitych $x_i,y_i$ ($-2\,000 \le x_i \le 2\,000$, $0 \le y_i \le 2\,000$) to współrzędne kolejnych wierzchołków wielokąta. Ciężar jest przymocowany do pierwszego wierzchołka, a co najmniej dwa wierzchołki leżą na osi $x$.

Wyjście

Wypisz zakres mas (w kilogramach), które można przymocować do żurawia bez jego przewrócenia. Jeśli zakres to $[a,b]$, wypisz $\lfloor a\rfloor$ .. $\lceil b\rceil$. Na przykład dla zakresu $[1.5,13.3]$ wypisz 1 .. 14. Jeśli zakres to $[a,\infty)$, wypisz $\lfloor a\rfloor$ .. inf. Jeśli żuraw nie może utrzymać żadnego ciężaru, wypisz zamiast tego unstable.

Przykład

Wejście 1

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

Wyjście 1

0 .. 1017

Wejście 2

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

Wyjście 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.