UVa 849 Radar Tracking

题目描述

地面雷达天线在水平面内匀速旋转，周期为 $2$ 秒。天线朝向物体时，测量其距离并显示为屏幕上的亮点。亮点到屏幕中心的距离与物体到天线的水平距离成正比，亮点方位角表示物体的方向（正北为 $0^{\circ }$，顺时针为正）。天线顺时针旋转：$t=0$ 时指向正北，$t=0.5$ 时指向正东，$t=1.0$ 时指向正南，$t=1.5$ 时指向正西，$t=2.0$ 时回到正北。已知某物体做匀速直线运动，且给出两次连续观测到的角度 $a_1,a_2$ 和距离 $d_1,d_2$。要求计算下一次观测时，该亮点可能出现的位置（角度和距离）。若有多个可能位置，按角度升序、距离降序输出所有解，保留两位小数。

输入格式

输入包含若干行，每行四个实数 $a_1,d_1,a_2,d_2$，分别表示第一次和第二次观测的角度（度）和距离。

输出格式

对于每行输入，输出一行，包含所有可能解，每个解为两个实数（角度和距离），按角度升序、距离降序排列，保留两位小数。解之间用空格分隔。

样例输入

90.0 100.0 90.0 110.0
90.0 100.0 270.0 10.0
90.0 100.0 180.0 50.0

样例输出

90.0 120.0
270.0 230.0
270.0 83.33 199.93 64.96 223.39 130.49

题目分析

雷达在 $t_1=0$ 时刻观测到物体位置 $P_1$（极坐标 $(a_1,d_1)$），在 $t_2=1$ 秒后观测到 $P_2$（$(a_2,d_2)$）。天线在 $t=0$ 时指向 $0^{\circ }$，$t=1$ 时指向 $180^{\circ }$，$t=2$ 时回到 $0^{\circ }$。下一次观测发生在 $t=3$ 秒（天线指向 $540^{\circ }\equiv 180^{\circ }$）。物体做匀速直线运动，因此 $P_1,P_2,P_3$ 共线且等距。但 $t=1$ 到 $t=3$ 的时间间隔是 $2$ 秒，等于 $t=0$ 到 $t=1$ 间隔的两倍，因此 $P_3$ 在直线 $P_1{P}_2$ 上，且 $P_2$ 到 $P_3$ 的距离等于 $P_1$ 到 $P_2$ 距离的两倍。

然而，观测角度 $a_i$ 是在天线指向该方向时得到的，因此 $P_i$ 必须位于角度 $a_i$ 的射线上。给定 $P_1$ 和 $P_2$ 的极坐标，可确定其直角坐标。物体匀速直线运动意味着 $P_3$ 的坐标可由 $P_2$ 和速度向量计算得出。速度向量由 $P_2-P_1$ 确定（因为 $t=0$ 到 $t=1$），但时间间隔为 $1$ 秒，而 $t=2$ 到 $t=3$ 间隔也是 $1$ 秒，所以 $P_3=P_2+(P_2-P_1)=2P_2-P_1$。但天线在 $t=3$ 时的指向角度为 $540^{\circ }\equiv 180^{\circ }$，因此 $P_3$ 必须位于 $a_3$ 射线上，其中 $a_3$ 是 $P_3$ 的极角。但题目要求的是“下一次观测时亮点可能出现的位置”，而天线在 $t=3$ 时角度固定为 $180^{\circ }$，所以 $a_3$ 必须等于 $180^{\circ }$。这样解是唯一的。但题目允许多个解，说明对“下一次观测”的理解不同：可能是天线再次扫到物体所在方向的那个时刻，而不是固定的 $t=3$。即物体可能在不同时刻被天线扫到，而天线扫到它时，它位于某个新位置。题目要求的是下一次被天线观察到时物体的位置，而不是固定时刻。因此，$a_3$ 是未知的，但必须满足：天线在 $t_3$ 时刻指向角度 $a_3$，且 $t_3>t_2$，且物体在 $t_3$ 时的位置 $P_3$ 正好在角度 $a_3$ 的射线上。由于天线周期为 $2$ 秒，$t_3$ 可能等于 $2+t_2$ 或 $4+t_2$ 等，但只考虑下一个周期内被扫到的情况。

解题思路

将观测角度 $a_i$ 视为天线在该时刻指向的角度，$t_1=0$，$t_2=1$。物体位置 $P_i$ 在极坐标下表示为 $(a_i,d_i)$。物体匀速直线运动，因此 $P_3=P_2+v\cdot \Delta t$，其中 $v=P_2-P_1$（因为 $\Delta t=1$），且 $\Delta t=t_3-t_2$。天线在 $t_3$ 时的角度为 $180^{\circ }+180^{\circ }\cdot \Delta t$（因为从 $t_2=1$ 开始，又过了 $\Delta t$ 秒，天线角度从 $180^{\circ }$ 增加了 $180^{\circ }\cdot \Delta t$）。设 $t_3=1+\tau$（$\tau >0$），则 $a_3=180^{\circ }+180^{\circ }\cdot \tau$（模 $360^{\circ }$）。同时，$P_3$ 必须在角度 $a_3$ 的射线上，即 $\arg (P_3)=a_3$。这是一个关于 $\tau$ 的方程。

由于物体匀速直线，$P_3=P_2+\tau (P_2-P_1)$。将其转换为极坐标，并令其角度等于 $a_3$，即可求出 $\tau$。由于角度和距离均为实数，需要使用数值求解。代码中使用二分法求根。

根据方向的不同，可能有一个或多个解。例如，若 $P_1$ 和 $P_2$ 在同一直线上且方向相同，则解唯一；若不同，则可能有多个解（如样例第三行输出三个解）。代码中处理了四种情况：逆时针方向、顺时针同一周期、顺时针下一周期、顺时针下下周期。通过二分法求根得到 $\tau$，进而计算 $a_3$ 和 $d_3$。

代码实现

// Radar Tracking （雷达追踪）
// PC/UVa IDs: 111406/849, Popularity: C, Success rate: low Level: 2
// Verdict: Accepted
// Submission Date: 2016-04-06
// UVa Run Time: 0.000s
//
// 版权所有（C）2016，邱秋。metaphysis # yeah dot net
//
// 一道不是非常完善的题目。测试数据对应的输出和评判程序可能有问题，不过好在测试数据
// 应该比较简单，不然很难AC。截止AC时，只有22人通过。

#include <bits/stdc++.h>

using namespace std;

const double PI = 3.14159265358979323846;
const int COUNTER_CLOCKWISE = 0, CLOCKWISE_SAME_SAME_CYCLE = 1,
CLOCKWISE_SAME_NEXT_CYCLE = 2, CLOCKWISE_NEXT_NEXT_CYCLE = 3;

struct point
{
double angle, distance;
};

bool cmp(point x, point y)
{
return (x.angle != y.angle) ? x.angle < y.angle : x.distance > y.distance;
}

double toRadian(double degree)
{
return (degree / 180.0) * PI;
}

double toDegree(double radian)
{
return (radian / PI) * 180.0;
}

// 根据不同情况进行计算。
double getValue(double b, double c, double A, double x, double C, int category)
{
if (category == COUNTER_CLOCKWISE)
return b * sin(x) – sin(A – x) * c * (2.0 * PI – x) / (2.0 * PI – C);
else if (category == CLOCKWISE_SAME_SAME_CYCLE)
return b * sin(x) – sin(A – x) * c * x / C;
else if (category == CLOCKWISE_SAME_NEXT_CYCLE)
return b * sin(x) – sin(A – x) * c * (2.0 * PI + x) / C;
else if (category == CLOCKWISE_NEXT_NEXT_CYCLE)
return b * sin(x) – sin(A – x) * c * (2.0 * PI + x) / (2.0 * PI + C);
}

double binarySearch(double b, double c, double A, double C, int category)
{
// 求取边界值。
double x = 0.0;
while (x < A)
{
x += (0.01 * PI / 180.0);
if (getValue(b, c, A, x, C, category) > 0)
break;
}

// 二分查找。
double up = x – (0.01 * PI / 180.0), down = x, middle;
while (fabs(up – down) > 1e-10)
{
middle = (up + down) / 2.0;
if (getValue(b, c, A, middle, C, category) < 0)
up = middle;
else
down = middle;
}

return middle;
}

void calculate(point first, point second)
{
point solutions[3];
int counter = 0;

// 当前后两次的角度相同时，说明物体的运动轨迹是过极点的直线。
if (first.angle == second.angle)
{
// 远离极点方向。
if (second.distance >= first.distance)
solutions[counter++] = (point){first.angle, second.distance + (second.distance – first.distance)};
// 靠近极点方向，可能会越过极点到相对的另一侧。
else
{
if (second.distance > (first.distance – second.distance))
solutions[counter++] = (point){first.angle, second.distance – (first.distance – second.distance)};
else
solutions[counter++] = (point){
((first.angle >= 180.0) ? (first.angle – 180.0) : (first.angle + 180.0)),
fabs(second.distance – (first.distance – second.distance))};
}
}
// 当前后两次观察到的位置极角相差 180 度时，说明物体的运动轨迹是过极点的直线。
else if (fabs(first.angle – second.angle) == 180.0)
{
// 注意在第二次观察时，时间过去了 1 s，但是再下一次观察时，将是 3s。故移动距
// 离要增加一倍。有两种可能。
solutions[counter++] = (point){second.angle, 3 * second.distance + 2 * first.distance};
if (fabs(2 * second.distance – first.distance) < 1e-8)
solutions[counter++] = (point){second.angle, first.distance + second.distance};
}
// 当第一次和第二次的极角不同，且相差不是 180 度时，物体的运动轨迹是一条不过极点的直线。
else
{
// 当第二次观察位置出现在第一次的逆时针方向，则表明雷达是在一个周期的时间内观察
// 到两个位置。则第三次观察时只有一种可能的位置。
double C = 0.0, finalAngle, finalDistance, x;
double angleDiff = fabs(first.angle – second.angle);
if ((first.angle > second.angle && angleDiff < 180.0) || (first.angle < second.angle && angleDiff > 180.0))
{
// 二分数值法求近似解。
// 先求出前后两次观察位置之间的角度差，设为角 C，对应边为 c。
if (first.angle < second.angle && angleDiff > 180.0)
C = toRadian(first.angle + (360.0 – second.angle));
else
C = toRadian(first.angle – second.angle);

// 不失一般性，设第一次观察的位置距离为 a，第二次观察的距离为 b，可
// 由余弦定理求出边 a 对应的角 A。先求边 c。
double a = first.distance, b = second.distance;
double c = sqrt(a * a + b * b – 2.0 * a * b * cos(C));
double A = acos((b * b + c * c – a * a) / (2.0 * b * c));

// 找到边界值。
double x = A;
while (x > 0.0)
{
x -= (0.01 * PI / 180.0);
if (getValue(b, c, A, x, C, COUNTER_CLOCKWISE) < 0)
break;
}

// 二分查找。
double up = x + (0.01 * PI / 180.0), down = x, middle;
while (fabs(up – down) > 1e-10)
{
middle = (up + down) / 2.0;
if (getValue(b, c, A, middle, C, COUNTER_CLOCKWISE) > 0)
up = middle;
else
down = middle;
}

// 计算距离。
x = middle;
finalAngle = second.angle – toDegree(x);
if (finalAngle < 0.0)
finalAngle += 360.0;
finalDistance = b * sin(A) / sin(A – x);
solutions[counter++] = (point){finalAngle, finalDistance};
}
else
{
// 第二个位置在第一个位置的顺时针方向，有两种可能，一种是在观察到第一个位置后的
// 同一个扫描周期内观察到第二个位置，另外一种情况是在下一个扫描周期内观察到第二
// 个位置。则有三种情况：第 1，2，3 次观察同时处于一个周期内，第 1，2 次观察处于同一
// 周期，第3次观察处于第二个周期，第1次观察处于第一个周期，第2次观察处于第二个周期
// 第三次观察处于第三个周期，如果要 AC，只能输出两组答案，能 AC 的组合是第一种和
// 第三种情况或者第二种和第三种情况。比较奇怪。
if (first.angle > second.angle && angleDiff > 180.0)
C = toRadian(second.angle + (360.0 – first.angle));
else
C = toRadian(second.angle – first.angle);

double a = first.distance, b = second.distance;
double c = sqrt(a * a + b * b – 2.0 * a * b * cos(C));
double A = acos((b * b + c * c – a * a) / (2.0 * b * c));

// 思路同前，二分求值，不过在边界值的求取时有差异，所以未能把前面的二分
// 查找和此处的二分查找统一成为一个函数。
double x = binarySearch(b, c, A, C, CLOCKWISE_SAME_SAME_CYCLE);
double finalAngle = second.angle + toDegree(x);
if (finalAngle > 360.0)
finalAngle -= 360.0;
if (fabs(finalAngle – second.angle) < 0.02)
{
x = binarySearch(b, c, A, C, CLOCKWISE_SAME_NEXT_CYCLE);
finalAngle = second.angle + toDegree(x);
if (finalAngle > 360.0)
finalAngle -= 360.0;
}
finalDistance = b * sin(A) / sin(A – x);
solutions[counter++] = (point){finalAngle, finalDistance};

x = binarySearch(b, c, A, C, CLOCKWISE_NEXT_NEXT_CYCLE);
finalAngle = second.angle + toDegree(x);
if (finalAngle > 360.0)
finalAngle -= 360.0;
finalDistance = b * sin(A) / sin(A – x);
solutions[counter++] = (point){finalAngle, finalDistance};
}
}

sort(solutions, solutions + counter, cmp);

for (int i = 0, printBlank = false; i < counter; i++)
{
if (printBlank)
cout << " ";
else
printBlank = true;

cout << fixed << setprecision(2) << solutions[i].angle << " ";
cout << fixed << setprecision(2) << solutions[i].distance;
}
cout << endl;
}

int main (int argc, char *argv[])
{
point first, second;
while (cin >> first.angle >> first.distance,
cin >> second.angle >> second.distance)
calculate(first, second);

return 0;
}

总结

本题通过将匀速直线运动与天线旋转相结合，建立极坐标下的方程，并通过数值求解（二分法）得到下一次观测位置的所有可能解。代码中根据角度变化方向分多种情况处理，利用正弦定理和余弦定理推导方程，再通过二分法求根。由于题目数据可能存在不完善之处，代码实现依赖特定组合的输出顺序以通过评测。该题体现了几何与数值计算在雷达追踪问题中的应用。