P4518 [JSOI2018] Counterattack

Thanks to your excellent performance, the aliens’ attack has been successfully repelled. Now, ``JYY`` has assembled the powerful Golden Fleet, ready to destroy the alien mothership in a single strike. The Golden Fleet has $n\,(n\ge 3)$ ships. These ships can focus their energy at a single point (the mothership’s location) to deliver a devastating blow. ``JYY`` plans to warp all ships near the mothership simultaneously and launch an attack instantly to end the battle. After the warp, due to various instabilities, the ships are not in optimal attack positions and must be adjusted quickly. Now all ships have completed the warp at the same time, and each ship can be viewed as a point on the plane. The $i$-th ($1\le i\le n$) ship is at coordinates $(x_i, y_i)$. The alien mothership is at the origin $(0, 0)$. To achieve the most effective strike, all ships must move onto the attack orbit. The attack orbit is the circle centered at $(0, 0)$ with radius $R$. Because the energy released is extremely large, ``JYY`` wants the distances between ships at the moment of firing to be as large as possible. Specifically, ``JYY`` wants all $n$ ships of the Golden Fleet to be evenly arranged on the attack orbit (all ships are identical, so any order is acceptable), that is, the distances along the arc between adjacent ships on the attack orbit are equal and exactly $\frac{2\pi R}{n}$. In other words, ``JYY`` wants to adjust all ships so that they all lie on the attack orbit and are exactly at the $n$ vertices of a regular $n$-gon. Please help ``JYY`` compute the minimum time to start the strike (i.e., the least time for all ships to move onto the attack orbit and be equally spaced). A ship can move one unit of distance per unit of time in the plane, and the volume of a ship can be considered $0$. Therefore, in your plan, it is allowed for ships to “meet” at some moment. Initially, ships’ coordinates are also allowed to coincide.

The first line contains two integers $n, R$, representing the number of ships and the radius of the attack orbit. The next $n$ lines each contain two integers $(x_i, y_i)$, representing the coordinates of each ship.

Output one line: the minimum time for all ships to be in position (print with sufficient precision). Your answer is considered correct if the absolute error from the reference answer does not exceed $10^{-6}$.

- For $20\%$ of the testdata, $n = 3$. - For $50\%$ of the testdata, $n \le 50$. - For $100\%$ of the testdata, $3 \le n \le 200$, $0 \le \lvert x_i \rvert, \lvert y_i \rvert, R \le 100$. Translated by ChatGPT 5