CF780H Intranet of Buses

A new bus route is opened in the city . 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.

N/A

N/A

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