SP11770 RPLL - Lifesavers

German 担任海洋救援组织（RPL）的负责人，他负责在船只沉没后指挥搜救工作。搜救范围根据船只沉没的时间确定，German 擅长数学，所以他总是知道这个时间值。然而，他不擅长计算合适的搜索范围，这有时会导致船只超出搜索区域，影响救援效率。 German 每次总会派出三艘船来确保搜救工作有效，但他不能派出所有船只，所以他希望这三艘船能覆盖最大面积。German 的船只比较简单，它们只会朝着某一个固定方向，以恒定速度前进。每个单位时间船只会移动一次。 当由三艘船组成的区域（三角形区域）的面积小于或等于 German 所给出的最大搜索面积时，表示该区域被覆盖。 German 会提供三艘船的初始坐标（二维坐标）、前进方向以及每小时的速度。救援船的方向只能是北、南、东或西中的一个，并且提供最大搜索面积。需要注意的是，三艘船所覆盖的三角形面积不能超过给定的最大面积。

第一行为一个整数 $T$，表示有 $T$ 组测试用例。接下来每组测试用例由 4 行组成：第一行是一个整数，表示最大搜索面积；接下来的三行分别包含三个整数和一个字符串，表示船只的坐标、方向和速度。

对于每个测试用例，输出「Scenario #i:」这个字符串，$i$ 表示当前分析的测试用例编号，然后是三艘船覆盖最大可能面积（不超过给定最大面积）所需的时间。时间是离散的。 **输入样例** ``` 2 150 1 4 north 2 2 0 south 2 3 1 east 2 12 0 -2 north 1 0 0 north 2 0 0 east 3 ``` **输出样例** ``` Scenario #1: 5 Scenario #2: 2 ```

- $1 \le T \le 100$ - $-10^6 \le X, Y \le 10^6$ - $1 \le \text{Speed} \le 10$ 小规模输入（30%） 在“小”规模的测试用例中，三角形始终是直角三角形，因此它们的面积相对容易计算。 - $1 \le \text{Max\_Area\_Of\_Searching} \le 10^3$ 大规模输入（70%） 任意三角形可形成，且这些数据的时间限制更为严格。 - $10^3 \le \text{Max\_Area\_Of\_Searching} \le 10^9$ 第二个样例的说明： 在第二小时，第一艘船的位置是 $(0,0)$，第二艘船的位置是 $(0,4)$，第三艘船的位置是 $(6,0)$。计算这些点构成的三角形的面积，我们得到 12。因为任何其他可能的面积都无法在不超过最大值的情况下满足条件，我们输出 2。 可以保证三艘船总是相互远离，因此下一个计算得到的面积总是会更大。 **本翻译由 AI 自动生成**