Start: Jun, 21, 2017 00:00:00
2017暑期短学期题库(part 5)
End: Jul, 05, 2017 12:00:00
Time elapsed:
Time remaining:

一笔画小游戏 2109

Time Limit:  1 s      Memory Limit:   128 MB Special Judge
Submission:250     AC:97     Score:1

Description

在一个正 n边形上,将 n条边的中点连结,形成一个新的正 n 边形,之后再在新的正 n 边形内连结各个中点,如此重复 k次,作为游戏的初始图案。

玩家要从初始图案最外层 n个顶点中的一个出发,进行无公共 端点 的一笔画。

端点 包含:

  1. 起点

  2. 终点

  3. 一笔画中方向发生改变的顶点。

画出的长度即为最后的得分,求玩家在给定的图形上最多能得多少分。

比如在一个边长为 100k=1 的正方形图案上进行一笔画,最优的方案如下:

Input

第一行一个整数T,代表有T组数据。

每组输入第一行有 2 个用一个空格分隔的整数 n(3<=n<=100)和 k(0<=k<=20)n为边数,k为重复次数。

第二行有一个浮点数 L(0<L<10^3),表示最外层正 n边形的边长。

Output

每组输出一行,表示最多能得多少分。结果误差在 10^-3以内均被认为是正确的。

Samples

input
3 4 0 100 4 1 100 5 4 8.300000
output
300 562.1320343 126.0120810598