地球表面等距点计算问题题解

问题描述

我们需要计算地球上两个点之间的等距点集合（大圆），然后计算第三个点到这个等距点集合的最短距离。地球被建模为半径为6378公里的完美球体。

解题思路

1. 坐标转换：将经纬度转换为三维直角坐标系坐标
2. 等距大圆计算：找到两个给定点的垂直平分大圆
3. 距离计算：计算第三个点到等距大圆的最短距离

关键步骤

1. 球面坐标转换：将经纬度转换为(x,y,z)坐标
2. 等距平面计算：计算两个点之间的垂直平分平面
3. 距离计算：计算点到平面的距离，然后转换为球面距离

标程

#include <bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
#define LL long long
#define mem(i,j) memset(i,j,sizeof(i))
#define inc(i,j,k) for(int i=j;i<=k;i++)
#define dec(i,j,k) for(int i=j;i>=k;i--)
const int N=1e5+5;
const double eps=1e-8;
const double PI=acos(-1.0);

// 浮点数比较函数
int dcmp(double x) {
    if(abs(x)<eps) return 0;
    else return x<0 ? -1:1;
}

// 三维点结构体
struct P {
    double x,y,z;
    P(){}
    P(double x,double y,double z):x(x),y(y),z(z){}
    P operator -(const P& p)const { return P(x-p.x,y-p.y,z-p.z); }
    double dot(const P& p) const { return x*p.x+y*p.y+z*p.z; }
    bool operator ==(const P& p)const {
        return dcmp(x-p.x)==0 && dcmp(y-p.y)==0 && dcmp(z-p.z)==0;
    }
}p[1005];

// 角度转弧度
double Radian(double t) {
    return t*PI/180.0;
}

// 向量长度
double lenP(P p) {
    return sqrt(p.dot(p));
}

// 计算两向量夹角
double Angle(P a,P b) {
    return acos(a.dot(b)/lenP(a)/lenP(b));
}

int tot; // 位置计数
map<string,int>id; // 位置名称到索引的映射
double R=6378.0; // 地球半径

// 输出格式化函数
void ptf(string c,int res,string a,string b) {
    cout<<c<<" is ";
    if(res==-1) cout<<"?";
    else cout<<res;
    cout<<" km off "<<a<<"/"<<b<<" equidistance.\n";
}

int main()
{
    ios::sync_with_stdio(false);
    id.clear(); tot=0;

    // 读取位置数据
    string s;
    double la,lo;
    while(cin>>s) {
        if(s=="#") break;
        id[s]=++tot;
        cin>>la>>lo;
        // 将经纬度转换为三维坐标
        p[tot].x=R*cos(Radian(la))*sin(Radian(lo));
        p[tot].y=R*cos(Radian(la))*cos(Radian(lo));
        p[tot].z=R*sin(Radian(la));
    }

    // 处理查询
    string A,B,C;
    while(cin>>A) {
        if(A=="#") break;
        cin>>B>>C;

        int aid,bid,cid;
        bool flag=0;

        // 检查位置是否存在
        if(!id.count(A)) flag=1; else aid=id[A];
        if(!id.count(B)) flag=1; else bid=id[B];
        if(!id.count(C)) flag=1; else cid=id[C];

        double ans, ang;
        if(flag) ans=-1.0; // 有位置不存在
        else {
            P a=p[aid], b=p[bid], c=p[cid];
            if(a==b) ans=0.0; // 两点相同
            else {
                // 计算点到等距大圆的距离
                ang=Angle(a-b,c); 
                ang=abs(ang-PI/2.0); 
                ans=ang*R+0.5; // 弧长公式并四舍五入
            }
        } 
        ptf(C,(int)ans,A,B); // 输出结果
    }

    return 0;
}

关键点解析

1. 坐标转换：

   • 将经纬度(φ,θ)转换为三维坐标(x,y,z)
   • x = R·cosφ·sinθ
   • y = R·cosφ·cosθ
   • z = R·sinφ

2. 等距大圆计算：

   • 两个点A和B的等距点集合是垂直于AB连线的平面与球面的交线
   • 通过计算向量夹角来确定点到等距大圆的距离

3. 距离计算：

   • 计算点C到向量AB的夹角
   • 计算与90度（垂直）的差值
   • 使用弧长公式转换为实际距离

4. 输入处理：

   • 使用map存储位置信息以便快速查找
   • 处理查询时检查所有位置是否存在

复杂度分析

• 时间复杂度：O(n + q)，其中n是位置数量，q是查询数量
• 空间复杂度：O(n)，用于存储位置信息

该解决方案高效地处理了球面几何问题，并考虑了所有边界情况，如极点和未知位置。