Intranet of Buses
Contest: Технокубок 2017 - Финал (только для онсайт-финалистов)
Difficulty rating: 3100
Tags: binary search, geometry, implementation, two pointers

A new bus route is opened in the city $$N$$. The route is a closed polygon line in the place, with all segments parallel to one of the axes. m buses will operate on the route. All buses move in a loop along the route in the same direction with equal constant velocities (stopping times are negligible in this problem).

Buses start their movement in the first vertex of the route with equal interval. Suppose that T is the total time for a single bus to travel the whole loop of the route. Then, the bus 1 starts moving at time 0, the bus 2 starts at time T / m, the bus 3 starts at time 2T / m, and so on; finally, the bus m starts moving at time (m - 1)T / m. Thus, all intervals between pairs of consecutive buses (including the interval between the last and the first bus) are equal.

Buses can communicate with each other via wireless transmitters of equal power. If the transmitters have power D, then only buses within distance D of each other can communicate.

The buses are also equipped with a distributed system of schedule tracking. For all buses to stick to the schedule, the system has to synchronize the necessary data between all buses from time to time. At the moment of synchronization, the bus 1 communicates with the bus 2, the bus 2 — with bus 3, and so on; also, the bus m communicates with the bus 1.

As a research employee, you are tasked with finding the smallest value of D such that it is possible to find a time moment to perform synchronization once all buses have started moving.

Input format:
The first line contains two integers n and m (2 ≤ n, m ≤ 105) — the number of vertices of the polygonal line, and the number of buses respectively.

Next n lines describe the vertices of the route in the traversing order. Each of these lines contains two integers xi, yi ( - 1000 ≤ xi, yi ≤ 1000) — coordinates of respective vertex.

It is guaranteed that each leg of the route (including the leg between the last and the first vertex) is paralles to one of the coordinate axes. Moreover, no two subsequent vertices of the route coincide. The route is allowed to have self-intersections, and travel along the same segment multiple times.

Output format:
Print one real number — the answer to the problem. Your answer will be accepted if the relative or the absolute error doesn't exceed 10 - 6.

Constraints:
Time limit: 10.0 s
Memory limit: 256.0 MB

Note:
Suppose that each bus travel 1 distance unit per second.

In the first sample case, in 0.5 seconds buses will be at distance 1, hence we can choose D = 1.

In the second sample case, in 0.5 seconds both buses will be at (0.5, 0), hence we can choose D = 0.

Example input:
4 2
0 0
0 1
1 1
1 0

Example output:
1.000000000

Example input:
2 2
0 0
1 0

Example output:
0.000000000

Editorial:
Let us do a binary search on the answer. Inside it, we have to check if at any time moment bus pairs 1 and 2, 2 and 3, ..., n and 1 are within distance x of each other simultaneously.
Let p(t) be the location of the bus 1 (that departed at time 0) at time t. Let us call a time moment t good, if we have ||p(t + T / m) - p(t)|| ≤ x, with ||a - b|| equal to the distance between points a and b. If there is a moment t such that t, t + T / m, ..., t + (m - 1)T / m are all good, then the answer is at least x.
We can build the two-dimensional graph (as in "function graph", not "graph with vertices and edges") of p(t + T / m) - p(t) over time by keeping track of segments where points p(t) and p(t + T / m) are. When the points are bounded to a pair of sides, the vector p(t + T / m) - p(t) changes linearly in time. There are O(n) time moments when either point switches from side to side, hence the difference graph can be constructed in O(n) time with the two pointers approach.
Now, for a certain x let's find the set of good moments t. We will do this separately for each segment of the difference graph, and then paste the answers. We have the condition ||q|| ≤ x, where q ranges over a segment. This is the segment-circle intersection problem, which is a standard geometrical primitive, with various approaches from solving quadratic equations to rotating a certain vector by an angle. In any case, the result will be a time range or an empty set. Note that q may stay still for a certain time range of the graph, which should be treated separately.
To ensure that p(t), p(t + T / m), and so on are all good for certain t, let us "cut" the segment [0, T] into m equal parts and superimpose them, with "good" segments possibly being cut into parts, now overlapping each other. A suitable moment t is now a point that is covered m times. Finding such point is a simple scan-line application.
Complexity: $${\mathcal O}(n\log\varepsilon^{-1})$$, where ε is the required relative precision.