1

我有一个问题要从类似 SPOJ的平台上解决,我不知道如何解决这个问题。这是问题,用 G 翻译器翻译,但如果丢失了我可以尝试更好地翻译它

该条目给出了测试的数量 T (10 <= T <= 100)。对于每个测试,给出数字 N (3 <= N <= 100)。这个数字是边为 1 的等边 N 角(例如,等边五边形,N = 5)。在 N 边形的 N 个顶点中的每一个上都播种了蜗牛。每只蜗牛作为“目标”都设置了一只蜗牛去到达另一只蜗牛——站在相邻顶点的那个(事实上,相邻节点选择的方向始终相同,即每只蜗牛“追逐”只是一个螺丝,每只蜗牛都被一只蜗牛“追逐”——蜗牛在开始时只做出一次选择,直到追逐结束才改变)。有那么一刻,蜗牛开始朝着它的目标移动(在任何时候都与它的目标完全成一条直线)。它一直持续到所有蜗牛在某一时刻都没有相互接触。为了更好地说明这种情况,请看下图:

图解说明

箭头显示如何选择目标,每只蜗牛。十字表示所有人相互接触的大致位置。你的任务是确定每只蜗牛的距离(所有蜗牛的距离都完全相同)。如果结果多于两位小数,则四舍五入小数点后第二位。

总之:

输入

测试次数 T

在接下来的 T 行 N

输出

对于每次测试,追逐过程中每只蜗牛的距离(结果四舍五入到小数点后两位)。

样本输入:

5

3

5

7

9

91

输出:

0.67

1.45

2.66

4.27

419.69

我的愿望是有人向我解释了如何从样本输入中获得所需的输出,并可能提出一些我可以使用的算法。

提前感谢您的时间

4

2 回答 2

2

你需要一些物理在这里。从其中一只蚂蚁的参照系来看。所以一只蚂蚁总是朝着它移动。现在沿着加入蚂蚁的线取相对速度。这将是 v(1-cos(2*pi)/N)(解决这个问题。这很容易)

现在它们在位移等于边长时相遇。因此所用时间为 1/v(1-cos((2*pi)/n))。行驶距离为 v*t,因此距离为 1/(1-cos((2*pi)/N))。

您可以在此处查看直接公式。

http://mathworld.wolfram.com/MiceProblem.html

于 2012-05-28T14:35:58.887 回答
1

您也可以这样看:蜗牛从正多边形的顶点开始,因此,由于它们都以相同的速度移动并直接朝目标移动,因此它们将始终保持在正多边形的顶点。因此,从中心到蜗牛的射线与蜗牛运动方向之间的角度是恒定的。这意味着蜗牛的路径是对数螺旋

和 0z(t) = e^{ct}之间的对数螺旋部分的长度是。|z| = 1|c|/|Re c|

对于给定的情况,c = e^{2π i/N} - 1 = (cos(2π/N) - 1) + i*sin(2π/N)是(按比例缩放)螺旋的参数。

现在|c| = 2*sin(π/N)|Re c| = 1 - cos(2π/N) = 2*sin²(π/N),所以如果起点和汇合点之间的距离是 1,那么每只蜗牛都会移动1/sin(π/N)。但条件是多边形的边是1,而不是中心和顶点之间的距离,所以我们必须缩放。方便的是,如果中心和顶点之间的距离为 1,则边长为|c|,因此行进距离的公式简化1/|Re c| = 1/(1 - cos(2π/N)为边长为1(1)

(¹) 当然,这与@sukun007 的结果完全相同,只是得出的结果不同。

于 2012-05-28T15:09:51.047 回答