시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 (추가 시간 없음) 1024 MB56393969.643%

문제

As any photographer knows, any good sunset photo has the sun setting over the sea. In fact, the more sea that is visible in the photo, the prettier it is!

You are currently visiting the island Bellevue, and you would like to take a photo of either the sunrise to the east or the sunset to the west to submit it to Bellevue's Astonishing Photography Competition. By carefully studying the topographic maps, you managed to find the east-west profile of the island. Now you would like to know the maximal amount of sea that you could capture in a photo, measured as the viewing angle covered by water.

The profile of the island is given as a piecewise linear function consisting of $n-1$ segments between $n$ points. The island starts and ends at sea level. As an example, Figure B.1 shows the profile of the first sample case.

Note that the viewing angle of your lens is not large enough to capture the ocean to the east and west of the island in one shot. Also, the viewing angle of sea at sea level is $0$ degrees.

Figure B.1: The east-west profile of the island in the first sample case.

입력

The input consists of:

  • One line with an integer $n$ ($3\leq n\leq 50\,000$), the number of points.
  • $n$ lines with two integers $x_i$ and $y_i$ ($0\leq x_i, y_i \leq 50\,000$), a point in the east-west profile of the island.

It is guaranteed that the points are given from left to right ($x_1<x_2<\dots<x_n$) and that the island starts and ends at sea level ($y_1 = y_n = 0$). The interior of the island is all above sea level ($y_i > 0$ for $1<i<n$).

출력

Output the maximal viewing angle of sea you can see, in degrees.

Your answer should have an absolute or relative error of at most $10^{-6}$.

예제 입력 1

6
0 0
2 1
3 1
4 4
5 1
9 0

예제 출력 1

45

예제 입력 2

5
1 0
5 4
6 1
8 2
9 0

예제 출력 2

63.4349488

출처

ICPC > Regionals > Europe > Northwestern European Regional Contest > Benelux Algorithm Programming Contest > BAPC 2022 B번

  • 문제를 만든 사람: Ragnar Groot Koerkamp