410418: GYM104020 B Bellevue

Memory Limit:512 MB Time Limit:1 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

B. Bellevuetime limit per test1 secondmemory limit per test512 megabytesinputstandard inputoutputstandard output

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 below 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.

Input

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

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}$$$.

ExamplesInput
6
0 0
2 1
3 1
4 4
5 1
9 0
Output
45.00000000000000000000
Input
5
1 0
5 4
6 1
8 2
9 0
Output
63.43494882292201064375

加入题单

上一题 下一题 算法标签: