题解 P2013 【无线电测向】

· · 题解

计算几何水好题

读明题意后，我们可以画出以下这张图(借用样例说明)：

(其中，蓝色的直线为船的航线所在的直线
紫色与红色为灯塔相对于船的方位)

不难看出，其实就是已知两条直线，求出直线的交点，即为船当前的位置！！

由平面几何中直线的定义，我们知道，对于函数f(x)，它有一种形式叫做点斜式；

然后根据斜率的定义，我们可以求得一条直线的斜率可以以两个直线上的点的坐标决定：

那么则有：

tanα=\frac{y_1-y}{x_1-x} (x_1-x)\cdot tanα=y_1-y y=y_1-(x_1-x)\cdot tanα

将y分别由x_1，y_1，x_2，y_2表示得：

\left\{\begin{matrix}y=y_1-(x_1-x)\cdot tan\alpha &\\y=y_2-(x_2-x)\cdot tan\beta &\end{matrix}\right.

联立，得：

y_1-(x_1-x)=y_2-(x_2-x)

移项，得：

y_1-x_1tan\alpha+xtan\alpha=y_2-x_2tan\beta+xtan\beta x(tan\alpha-tan\beta)=y_2-y_1+x_1tan\alpha-x_2tan\beta x=\frac{y_2-y_1+x_1tan\alpha-x_2tan\beta}{tan\alpha-tan\beta}
所以，我们只需要对于每条直线，处理出它们的斜率(即tan\alpha，\alpha为直线与x轴倾斜角)

我们知道，题目给出的是航线与直线的夹角，而航线的方位是相对于y轴的夹角：

我们只需要求得该夹角的余角，即90^{\circ}-\theta(\theta为给出的夹角)。

同时，对于直线的倾斜角，我们处理它对于x轴的夹角时，是允许存在第四象限角的，即斜率为负。

所以我们这样处理：

double beta=180-an-an2;

其中an为航线的倾斜角，an1，an2分别表示两条位置所在的直线的夹角；

另外，当两直线斜率相同，则无解。

完整代码：

#include<bits/stdc++.h>
#define in inline
#define reg register
#define int long long
#define MAX 20030813
#define pi acos(-1)
using namespace std;
namespace qwq{
    in int read(int &o)
    {
        o=0;
        int w=1;
        char c=getchar();
        while(c<'0'||c>'9')
        {
            if(c=='-')w=-1;
            c=getchar();
        }
        while(c>='0'&&c<='9')
        {
            o=(o<<3)+(o<<1)+(c^48);
            c=getchar();
        }
        return o*w;
    }
    in void write(int x)
    {
        if(x>9)write(x/10);
        putchar(x%10+48);
    }
    in int max(int x,int y)
    {
        return x>y?x:y;
    }
    in int min(int x,int y)
    {
        return x<y?x:y;
    }
}
using namespace qwq;
int n;
class Tower
{
public:
    int x,y;
    char cnt;
}tow[MAX];
char c1,c2;
double _x1_,_x2_,_y1_,_y2_,x,y;
int alpha,beta,an,an1,an2;
signed main()
{
    read(n);
    for(reg int i=1;i<=n;++i)
    {
        cin>>tow[i].cnt;
        read(tow[i].x),read(tow[i].y);
    }
    read(an);
    an-=90;
    cin>>c1,read(an1);
    alpha=180-an-an1;
    cin>>c2,read(an2);
    beta=180-an-an2;  
        if(tan(pi/180*alpha)==tan(pi/180*beta))
        {
            puts("NO ANSWER");return 0;
        }
    for(reg int i=1;i<=n;++i)
    {
        if(c1==tow[i].cnt)_x1_=tow[i].x,_y1_=tow[i].y;
        if(c2==tow[i].cnt)_x2_=tow[i].x,_y2_=tow[i].y;
    }
    x=((_y2_-_y1_)+_x1_*tan(pi/180*alpha)-_x2_*tan(pi/180*beta))/(tan(pi/180*alpha)-tan(pi/180*beta));
    y=_y1_+(x-_x1_)*tan(pi/180*alpha);
    printf("%.2lf %.2lf\n",x,y);
    return 0;
}

在楼上两篇大佬的题解里，对于灯塔位置的映射是用map实现的，然而此题灯塔数量n\leq30，在下认为是不需要map的，直接 \Theta (n)扫描不就好啦？

若路过大佬在此停留，指点一二，蒟蒻不胜感激

Update in 19.8.15：感谢@RsXxy对于本文错误的指正。