UVA 10075 Airlines (Floyd + 数学转换)

题意：

告诉你n个点的经度 和 纬度， 告诉你m 个有向边， q 个查询 ，求两点的最短路。

思路：

显然裸floyd

就是这个两点之间距离比较恶心了。

我们直接以球心为圆点， 建立XYZ直角坐标系。

球心连接 经度 0 的位置。  

然后就好求 任意点的xyz 坐标了。

假设纬度 是wd（弧度）， 经度是jd（弧度）

那么

X = R * cos（wd） * cos（jd）

Y = R * cos（wd）*  sin（jd）

Z = R * sin（wd）

然后就可以利用余弦定理来求两点之间的角度了。  知道角度，半径 就可以求弧长了。

（给个图方便大家想像= =）

注意：

这个题要四舍五入

但到最后四舍五入是无法过样例的。

应该在计算 两点之间距离时就 要四舍五入了。 （这个样例要是没有， 得WA到死= =）

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <map>
#include <cmath>
#include <cstdlib>
#include <map>
#include <string>
using namespace std;

int n, m, q;
const int maxn = 100 + 7;
map<string, int>mp;
int cnt;
const double R = 6378;
const double pi = 3.141592653589793;

struct node{
    double wd, jd;
    double x, y, z;
    double calc(){
        x = R * cos(wd) * cos(jd);
        y = R * cos(wd) * sin(jd);
        z = R * sin(wd);
    }
}p[maxn];
char name[23];
int ID(string name){
    if (!mp.count(name)) return mp[name] = ++cnt;
    return mp[name];
}

double get(int i,int j){
    double tmp = (p[j].x - p[i].x) * (p[j].x - p[i].x) + (p[j].y - p[i].y) * (p[j].y - p[i].y) + (p[j].z - p[i].z) * (p[j].z - p[i].z);
    double st = (2*R*R - tmp) / (2*R*R);
    return acos(st) * R;
}

char s[23], t[23];

const long long inf = 1e10;
long long g[maxn][maxn];
int ks;

int up(double x){
    return (int)(x + 0.5);

}
int main(){

    while(~scanf("%d %d %d", &n, &m, &q) && (n || m || q)){

        cnt = 0;
        mp.clear();
        for (int i = 1; i <= n; ++i){
            scanf("%s", name);
            int pos = ID(name);
            scanf("%lf %lf", &p[pos].wd, &p[pos].jd);
            p[pos].wd = p[pos].wd * pi / 180;
            p[pos].jd = p[pos].jd * pi / 180;
            p[pos].calc();
        }

        for (int i = 1; i <= cnt; ++i){
            for (int j = 1; j <= cnt; ++j){
                g[i][j] = inf;
            }
        }


        for (int i = 0; i < m; ++i){
            scanf("%s%s", s, t);
            int p1 = ID(s), p2 = ID(t);
            g[p1][p2] = (long long)up(get(p1, p2));
        }

        for (int k = 1; k <= cnt; ++k){
            for (int i = 1; i <= cnt; ++i){
                for (int j = 1; j <= cnt; ++j){
                    g[i][j] = min(g[i][k] + g[k][j], g[i][j]);
                }

            }

        }


        if (ks++)puts("");
        printf("Case #%d\n", ks);

        while(q--){
            scanf("%s%s", s, t);
            int p1 = ID(s);
            int p2 = ID(t);

            if (g[p1][p2] >= inf) puts("no route exists");
            else printf("%lld km\n", g[p1][p2]);
        }



    }


    return 0;
}