QOJ.ac

QOJ

時間限制: 0.5 s 記憶體限制: 64 MB 總分: 100

#1487. 违禁品

统计

据报道,有物体从飞越海湾的飞机上掉落。警方认为该物体可能是某种违禁品,会被同伙捡走,因此他们希望在任何可能掉落该物体的飞机再次飞越海湾时进行监视。海湾周围已部署了三个夜视观测站(见下图)。

观测站 1 位于观测站 0 以东 $3.715$ 公里、以北 $1.765$ 公里处;观测站 2 位于观测站 0 以东 $2.894$ 公里、以南 $2.115$ 公里处。

当可疑飞机飞越海湾时,每位观测者都会使用夜视设备跟踪飞机,并与其他观测者保持联系。每位观测者都会记录一个指向物体的方向以及该方向的置信度(confidence level)。置信度($CL$)是一个介于 $0$(大致指向飞机)到 $1$(指向物体落入水中的溅落点)之间的值。

通常,三条视线不会交于一点,而是会形成一个三角形(见上图中的 Intersection Detail)。对实际位置的最佳估计是点 $(x, y)$,该点使得各点到每条直线的距离的平方和最小,并以置信度 $CL[i] + 0.2$ 加权:

$$\text{Minimize } \sum_{i=0}^{2} \{ (CL[i] + 0.2) * d[i]^2 \}$$

对于本题,你需要编写一个程序,输入三个观测者的方向和三个置信度,并输出点 $(x, y)$,该点使上述和最小。其中 $x$ 是距离观测站 0 以东的距离(公里),$y$ 是距离观测站 0 以北(正值)或以南(负值)的距离(公里)。

输入格式

输入的第一行包含一个整数 $P$ ($1 \le P \le 1000$),表示随后数据组的数量。每组数据应独立处理。

每组数据由单行组成,包含数据组编号 $N$,后跟一个空格,再后跟六个空格分隔的浮点数值。这些浮点数值依次为:$a[0], CL[0], a[1], CL[1], a[2], CL[2]$。其中 $a[i]$ 是观测站 $i$ 的方位角(以度为单位,从正北方向顺时针测量,$0 \le a[i] < 360$),$CL[i]$ 是观测者 $i$ 的置信度 ($0 \le CL[i] \le 1$)。

输出格式

对于每组数据,输出一行。包含数据组编号 $N$,后跟一个空格,然后是两个空格分隔的值 $x$ 和 $y$。$x$ 是距离观测站 0 以东的距离(公里),$y$ 是距离观测站 0 以北(正值)或以南(负值)的距离(公里)。距离应显示为 3 位小数。

样例

样例输入 1

3
1 44.0 0.38 272.9 0.41 345.5 0.64
2 43.5 0.80 263.6 0.81 338.2 0.83
3 45.9 0.50 279.2 0.78 348.7 0.81

样例输出 1

1 1.847 1.877
2 1.440 1.511
3 2.073 2.021

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.