#P4634. 转啊转啊转

    ID: 3781 传统题 1000ms 512MiB 尝试: 2 已通过: 1 难度: 8 上传者: 标签>CF2500提高+/省选-有限候选集缩减Andrew 算法Minkowski 和凸多边形边向量归并叉积自定义排序规则平方距离比较

转啊转啊转

P4634 转啊转啊转

题目描述

这一回,SHUXK 进入了浩瀚的宇宙!只是这个宇宙是二维的。

SHUXK 发现宇宙中有 NN 颗星球,他以自己的初始位置为原点,得到了这 NN 颗星球的坐标。

这个宇宙虽然只有二维,但仍然存在引力,而且非常奇特。SHUXK 发现自己可以操控引力进行旋转。准确地说,每一分钟,他可以选择下面两种操作之一:

  1. 选择一颗星球,使自己只受到这颗星球的引力,以该星球为旋转中心,顺时针旋转 90∘90^\circ,到达新的位置;
  2. 排斥所有星球的引力,留在原地不动。

星球的位置始终不变。

SHUXK 有 MM 分钟可以探索宇宙。他希望在恰好 MM 分钟后,自己与初始原点的距离尽可能大。

请计算这个最远距离。

输入格式

第一行包含两个正整数 N,MN,M,分别表示星球数量和分钟数。

接下来 NN 行,每行包含两个整数 Xi,YiX_i,Y_i,表示第 ii 颗星球的坐标。

输出格式

输出一个实数,表示 MM 分钟后 SHUXK 与原点的最大距离。

当输出与正确答案的相对误差不超过 10−610^{-6} 时,即认为答案正确。

样例输入

2 5
-1 1
-2 2

样例输出

6.324555

样例说明

一种达到最远距离的操作方案是:

  1. 第一分钟,绕 (−2,2)(-2,2) 顺时针旋转 90∘90^\circ,到达 (−4,0)(-4,0);
  2. 第二分钟,绕 (−2,2)(-2,2) 顺时针旋转 90∘90^\circ,到达 (−4,4)(-4,4);
  3. 第三分钟,绕 (−1,1)(-1,1) 顺时针旋转 90∘90^\circ,到达 (2,4)(2,4);
  4. 第四分钟,绕 (−1,1)(-1,1) 顺时针旋转 90∘90^\circ,到达 (2,−2)(2,-2);
  5. 第五分钟,绕 (−2,2)(-2,2) 顺时针旋转 90∘90^\circ,到达 (−6,−2)(-6,-2)。

最终距离为 (−6)2+(−2)2=40≈6.324555\sqrt{(-6)^2+(-2)^2}=\sqrt{40}\approx6.324555。

数据范围

对于 100%100\% 的数据:

  • 1≤N≤50001\le N\le5000;
  • 1≤M≤1081\le M\le10^8;
  • −1000≤Xi,Yi≤1000-1000\le X_i,Y_i\le1000,所有坐标均为整数。