17983번 - Drive Safely 스페셜 저지다국어

A new stretch of road has just been built from Askøy to Bergen. Before the road can be opened for the public, however, a decision needs to be made as for which speed limits to impose. The minister of transportation wants the travelling time from Askøy to Bergen to be as small as possible, but he also imposes some constraints:

• For safety reasons, the speed limit through a turn of α degrees can be at most |180−α| km/h. Even on a straight line, the speed limit can not exceed 180 km/h.
• To save money on sign costs, the minister of transportation will only allow k speed limit signs to be placed along the road.

The road is designed as a polyline, a sequence of n coordinates: the road starts in the first location, follows a straight line to the second location, from there follows a straight line to the third location, and so forth, until reaching the final location. Note that the road might cross itself with bridges or tunnels, but there will not be any intersections where a car can take a shortcut.

The speed limit is initially 180 km/h. Note that it is allowed to place two speed limit signs very close to each other, and the minister of transportation will allow speed limit signs to hold decimal values with infinite precision.

The first line of input contains two positive integers n (2 ≤ n ≤ 200), and k (1 ≤ k ≤ 50). On each of the next n lines follows the locations of the polyline describing the road, starting with where the road starts at Askøy, ending with where the road ends in Bergen. The i^th location is described by two real numbers x_i and y_i (−1 000 000 ≤ x_i, y_i ≤ 1 000 000), denoting the coordinates in kilometers away from the arbitrarily chosen origin. All turns are at most 179 degrees either clockwise or counterclockwise, and coordinates are given with at most 6 digits after the decimal point.

A single real number, the shortest possible travelling time from Askøy to Bergen (in hours). Any answer within an absolute or relative error of 10⁻⁶ will be accepted.