#P4634. 转啊转啊转
转啊转啊转
题目描述
这一回, SHUXK 进入了浩瀚的宇宙!只是这个宇宙是二维的。SHUXK发现这个宇宙中有N颗星球,他以自己所在的
位置为原点得到了这N颗星球的坐标。这个宇宙虽然是二维的,但是仍然存在引力,而且还非常奇特。 经过一番研
究之后, SHUXK 发现自己可以操控引力进行旋转。准确地说,每一分钟, 他可以选择一颗星球,使得自己只受到
那颗星球的引力,然后在引力的作用下绕着那颗星球顺时针旋转 90°来到一个新的位置。当然, SHUXK 在这一分
钟里也可以选择排斥所有星球的引力,保持原地不动。SHUXK 有M分钟的时间在这个宇宙中玩耍( M分钟以后梦就
醒了),他想要探索这个宇宙的深处,所以他希望自己在M分钟以后离原点越远越好。请你告诉他最远能离原点有
多远。
输入格式
第一行包含两个正整数N,M分别表示星球的数量和时间。
以下N行每行包含两个整数Xi,Yi表示一颗星球的坐标为(Xi,Yi)( -1000 ≤Xi,Yi ≤ 1000)
N<=5000,M<=10^8
输出格式
只有一行一个实数,表示 SHUXK在M分钟后离原点可能的最远距离。当你的答案与标准答案的相对误差不超过10^-6
时即视为正确。
2 5
-1 1
-2 2
6.324555
SHUXK 的二维宇宙冒险过程如下:
1. 第一分钟绕(-2,2)顺时针旋转 90°,来到(-4,0);
2. 第二分钟绕(-2,2)顺时针旋转 90°,来到(-4,4);
3. 第三分钟绕(-1,1)顺时针旋转 90°,来到(2,4);
4. 第四分钟绕(-1,1)顺时针旋转 90°,来到(2, -2);
5. 第五分钟绕(-2,2)顺时针旋转 90°,来到(-6, -2)。
最终 SHUXK 离原点的距离为Sqrt(40) ≈ 6.324555。