当前没有测试数据。

题目描述

海盗的藏宝图通常包含一系列指令，按照这些指令从登陆点出发，可以到达标记为$X$的藏宝地点。你需要为一个特定的荒岛设计这样的指令序列。

该岛屿是一个半径为$r$步的圆，圆心位于$(0,0)$。以圆心为参考：

• $(0,1)$方向为北
• $(0,-1)$方向为南
• $(1,0)$方向为东
• $(-1,0)$方向为西
• $(1,1)$方向为东北
• $(1,-1)$方向为东南
• $(-1,1)$方向为西北
• $(-1,-1)$方向为西南

登陆点位于岛屿的圆周上，由其坐标指定；标记为$X$的地点也由其坐标指定。

每条指令的格式应为：

方向 距离

其中，方向是以下之一：
{ north, south, east, west, northeast, northwest, southeast, southwest }
距离是一个非负实数，表示在该方向上移动的步数。指令序列的执行必须确保从登陆点出发，最终到达$X$点，且路径不离开岛屿。

要求：
$1$. 总距离（即所有指令的距离之和）最小化。
$2$. 在所有总距离最小的序列中，选择指令数量最少的序列。

输入格式

输入包含多个测试用例，以一行-1结束。每个测试用例占一行，包含五个实数：
$-$ $r$（岛屿半径）
$-$ $x$, $y$（登陆点坐标）
$-$ $X$, $Y$（$X$点坐标）

保证登陆点和$X$点不同。

输出格式

对于每个测试用例，逐行输出指令序列。距离需保留小数点后十位（如样例所示）。测试用例之间用空行分隔。

样例输入 1

100.0 0.0 100.0 25.0 50.0
-1

样例输出 1

south 25.0000000000
southeast 35.3553390593

来源

Waterloo local 2004.09.19