{"problem":{"name":"F. Intranet of Buses","description":{"content":"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 al","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":10000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF781F"},"statements":[{"statement_type":"Markdown","content":"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).\n\nBuses 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 2_T_ / _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.\n\nBuses 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.\n\nThe 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.\n\nAs 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\n## Input\n\nThe 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.\n\nNext _n_ lines describe the vertices of the route in the traversing order. Each of these lines contains two integers _x__i_, _y__i_ ( - 1000 ≤ _x__i_, _y__i_ ≤ 1000) — coordinates of respective vertex.\n\nIt 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.\n\n## Output\n\nPrint 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.\n\n[samples]\n\n## Note\n\nSuppose that each bus travel 1 distance unit per second.\n\nIn the first sample case, in 0.5 seconds buses will be at distance 1, hence we can choose _D_ = 1.\n\nIn the second sample case, in 0.5 seconds both buses will be at (0.5, 0), hence we can choose _D_ = 0.","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"城市新开通了一条公交线路。该线路是一条封闭的多边形折线，所有线段均平行于坐标轴之一。共有 #cf_span[m] 辆公交车在这条线路上运行。所有公交车沿线路同方向以相同的恒定速度循环行驶（本题中停站时间可忽略不计）。\n\n公交车从线路的第一个顶点出发，间隔相等。设 #cf_span[T] 为一辆公交车完整行驶一圈所需的时间，则公交车 1 在时间 0 出发，公交车 2 在时间 #cf_span[T / m] 出发，公交车 3 在时间 #cf_span[2T / m] 出发，依此类推；最后，公交车 #cf_span[m] 在时间 #cf_span[(m - 1)T / m] 出发。因此，任意相邻两辆公交车之间的间隔（包括最后一辆与第一辆之间的间隔）均相等。\n\n公交车之间通过功率相同的无线发射器进行通信。若发射器功率为 #cf_span[D]，则仅当两辆公交车之间的距离不超过 #cf_span[D] 时，它们才能通信。\n\n公交车还配备了一个分布式时刻表同步系统。为确保所有公交车准时运行，系统需要定期在所有公交车之间同步必要数据。同步时刻，公交车 1 与公交车 2 通信，公交车 2 与公交车 3 通信，依此类推；同时，公交车 #cf_span[m] 与公交车 1 通信。\n\n作为研究人员，你的任务是找出最小的 #cf_span[D] 值，使得在所有公交车均已启动后，存在一个时刻可以完成同步。\n\n第一行包含两个整数 #cf_span[n] 和 #cf_span[m]（#cf_span[2 ≤ n, m ≤ 10^5]）——分别表示多边形折线的顶点数和公交车数量。\n\n接下来 #cf_span[n] 行按遍历顺序描述线路的各个顶点。每行包含两个整数 #cf_span[xi], #cf_span[yi]（#cf_span[ - 1000 ≤ xi, yi ≤ 1000]）——表示对应顶点的坐标。\n\n保证线路的每一段（包括最后一个顶点与第一个顶点之间的线段）均平行于某一坐标轴。此外，任意两个相邻顶点不会重合。线路允许自交，也允许多次经过同一段线段。\n\n请输出一个实数——本题的答案。你的答案若相对误差或绝对误差不超过 #cf_span[10^{-6}]，则会被接受。\n\n假设每辆公交车每秒行驶 1 个单位距离。\n\n在第一个样例中，0.5 秒后两辆公交车相距 1，因此可选择 #cf_span[D = 1]。\n\n在第二个样例中，0.5 秒后两辆公交车均位于 #cf_span[(0.5, 0)]，因此可选择 #cf_span[D = 0]。\n\n## Input\n\n第一行包含两个整数 #cf_span[n] 和 #cf_span[m]（#cf_span[2 ≤ n, m ≤ 10^5]）——分别表示多边形折线的顶点数和公交车数量。接下来 #cf_span[n] 行按遍历顺序描述线路的各个顶点。每行包含两个整数 #cf_span[xi], #cf_span[yi]（#cf_span[ - 1000 ≤ xi, yi ≤ 1000]）——表示对应顶点的坐标。保证线路的每一段（包括最后一个顶点与第一个顶点之间的线段）均平行于某一坐标轴。此外，任意两个相邻顶点不会重合。线路允许自交，也允许多次经过同一段线段。\n\n## Output\n\n请输出一个实数——本题的答案。你的答案若相对误差或绝对误差不超过 #cf_span[10^{-6}]，则会被接受。\n\n[samples]\n\n## Note\n\n假设每辆公交车每秒行驶 1 个单位距离。\n\n在第一个样例中，0.5 秒后两辆公交车相距 1，因此可选择 #cf_span[D = 1]。\n\n在第二个样例中，0.5 秒后两辆公交车均位于 #cf_span[(0.5, 0)]，因此可选择 #cf_span[D = 0]。","is_translate":true,"language":"Chinese"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ n, m \\in \\mathbb{Z} $ with $ 2 \\leq n, m \\leq 10^5 $.  \nLet $ V = (v_0, v_1, \\dots, v_{n-1}) $ be a sequence of vertices in $ \\mathbb{R}^2 $, where $ v_i = (x_i, y_i) $, forming a closed polygonal route with axis-aligned segments.  \nLet $ L = \\sum_{i=0}^{n-1} \\|v_{i+1} - v_i\\| $ be the total length of the route (with $ v_n = v_0 $).  \nLet $ T = L $ be the time for one bus to complete the loop (since speed is 1 unit/sec).  \n\nLet $ B_k(t) \\in \\mathbb{R}^2 $ denote the position of bus $ k \\in \\{0, 1, \\dots, m-1\\} $ at time $ t \\geq 0 $, starting at vertex $ v_0 $ at time $ t_k = \\frac{kT}{m} $, and moving along the route with constant speed 1 in the given direction.  \n\nLet $ d_k(t) = \\|B_k(t) - B_{k+1 \\bmod m}(t)\\| $ be the Euclidean distance between consecutive buses at time $ t $, for $ k = 0, 1, \\dots, m-1 $.  \n\n**Constraints**  \n- The route is closed and axis-aligned.  \n- Buses start at times $ t_k = \\frac{kT}{m} $, equally spaced.  \n- All buses move with speed 1 along the fixed route.  \n\n**Objective**  \nFind the minimal $ D \\geq 0 $ such that there exists a time $ t \\geq 0 $ where:  \n$$\n\\max_{k \\in \\{0, \\dots, m-1\\}} d_k(t) \\leq D\n$$  \nThat is, at some time $ t $, all consecutive bus pairs (including $ B_{m-1} $ and $ B_0 $) are within distance $ D $, and we minimize this maximum distance.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF781F","tags":["binary search","geometry","two pointers"],"sample_group":[["4 2\n0 0\n0 1\n1 1\n1 0","1.000000000"],["2 2\n0 0\n1 0","0.000000000"]],"created_at":"2026-03-03 11:00:39"}}