UVa 10075 - Airlines

时间:2022-10-15 21:56:53

航线算球面距离,需要经纬度转空间坐标。

任意两点间距离用Floyd求出来,查询时直接查表。

 #include <cstdio>
#include <map>
#include <cmath>
#include <string>
#include <cstring>
#include <cstdlib> using namespace std; const int MAXN = ;
const double INF = 1e30;
const double eps = 1e-;
const double PI = acos( -1.0 ); struct Point
{
double x, y;
Point( int x = , int y = ): x(x), y(y) {}
}; struct Coordinate //空间坐标
{
double x, y, z;
}; double dist[MAXN][MAXN];
Coordinate C[MAXN]; double Cha( double a, double b )
{
return (a - b)*(a - b);
} double GetDis( Coordinate a, Coordinate b ) //三维空间直线距离
{
return sqrt( Cha( a.x, b.x ) + Cha( a.y, b.y ) + Cha( a.z, b.z ) );
} double toRad( double deg ) //角度转弧度
{
return deg / 180.0 * acos( -1.0 );
} void get_coord( double R, double lat, double lng, double &x, double &y, double &z ) //经纬度转空间坐标
{
lat = toRad(lat);
lng = toRad(lng);
x = R*cos(lat)*cos(lng);
y = R*cos(lat)*sin(lng);
z = R*sin(lat);
return;
} void Floyd( int n ) //弗洛伊德算任意两点最短路
{
for ( int k = ; k < n; ++k )
for ( int i = ; i < n; ++i )
for ( int j = ; j < n; ++j )
{
double temp = dist[i][k] + dist[k][j];
if ( temp < dist[i][j] ) dist[i][j] = temp;
}
return;
} int main()
{
int n, m, Q;
double r = ;
int cas = ;
bool flag = false;
while ( scanf( "%d%d%d", &n, &m, &Q ), n || m || Q )
{
map<string, int> Map;
for ( int i = ; i < n; ++i )
{
char str[];
Point P;
scanf("%s%lf%lf", str, &P.x, &P.y );
get_coord( r, P.x, P.y, C[i].x, C[i].y, C[i].z );
Map[ str ] = i;
} for ( int i = ; i <= n; ++i )
for ( int j = ; j <= n; ++j )
dist[i][j] = INF; for ( int i = ; i < m; ++i )
{
char str1[], str2[];
scanf( "%s%s", str1, str2 );
int u = Map[ str1 ];
int v = Map[ str2 ];
dist[u][v] = (int)( 2.0 * asin( GetDis( C[u], C[v] ) / ( 2.0 * r ) ) * r + 0.5 ); //四舍五入
} Floyd( n ); if ( flag ) puts(""); printf( "Case #%d\n", ++cas ); while ( Q-- )
{
char str1[], str2[];
scanf( "%s%s", str1, str2 );
int u = Map[ str1 ];
int v = Map[ str2 ];
if ( dist[u][v] >= INF - eps ) puts( "no route exists" );
else printf( "%.0f km\n", dist[u][v] );
} flag = true;
}
return ;
}