10075

Theory:

Distance

This uses the ‘haversine’ formula to calculate the great-circle distance between two points – that is, the shortest distance over the earth’s surface – giving an ‘as-the-crow-flies’ distance between the points (ignoring any hills they fly over, of course!).

Haversine formula:

a = sin²(Δφ/2) + cos φ1 * cos φ2 * sin²(Δλ/2) c = 2 * atan2( √a, √(1−a) ) d = R * c

R = Radius ; // km    φ1 = lat1 (in radian);    φ2 = lat2 (in radian);    Δφ = (lat2–lat1)(in radian);    Δλ = (lon2–lon1)(in radian);

a = sin(Δφ/2) * sin(Δφ/2) + cos(φ1) * cos(φ2) * sin(Δλ/2) * sin(Δλ/2);    c = 2 * atan2(sqrt(a), sqrt(1–a));     d = R * c;

Click here for more information

#include <iostream>
#include <cmath>
#include <map>
#include <cstring>
#include <string>
#include <cstdio>

#define Rad 6378
#define PI  3.141592653589793
#define INF 1000000000

using namespace std;

struct City{
	double lattitde;
	double longitde;
};

int gr[105][105];
map<string,int> mp;
City ct[105];
//http://www.movable-type.co.uk/scripts/latlong.html
double haversine(int i,int j)
{
	double latt1,latt2,lon1,lon2;
	double lattdiff,londiff;
	//radian = degree*(PI/180)
	latt1 = ct[i].lattitde *(PI/180);
	lon1 = ct[i].longitde *(PI/180);
	latt2 = ct[j].lattitde*(PI/180);
	lon2 = ct[j].longitde*(PI/180);

	lattdiff = latt1-latt2;//(ct[i].lattitde-ct[j].lattitde)*(PI/180);
	londiff = lon1-lon2;//(ct[i].longitde-ct[j].longitde)*(PI/180);

	double a = sin(lattdiff/2)*sin(lattdiff/2)+cos(latt1)*cos(latt2)*sin(londiff/2)*sin(londiff/2);

	double c = 2*atan2(sqrt(a),sqrt(1-a));
	double d = Rad*c;

	return d;
}


int main()
{
	int N,M,Q;
	int kase=1;
	string s,st1,st2;
	double lat,lon;
	while(cin>>N)
	{
		cin>>M>>Q;
		if(N+M+Q==0)
		break;
		mp.clear();
		//memset(gr,INF,sizeof(gr));
		for(int i=0;i<105;i++)
		{
			for(int j=0;j<105;j++)
			{
				if(i==j)
				gr[i][j]=0;
				else
				gr[i][j]=INF;
			}
		}
		//cout<<gr[5][7]<<"\n";
		int KK =1;
		while(N--)
		{
			cin>>s;
			cin>>lat>>lon;
			if(mp[s]==0)
			{
				mp[s]=KK;KK+=1;
			}
			ct[mp[s]].lattitde=lat;
			ct[mp[s]].longitde=lon;
		}
		while(M--)
		{
			cin>>st1>>st2;
			//haversine formulae
			double dist = haversine(mp[st1],mp[st2]);
			gr[mp[st1]][mp[st2]] = int(dist+0.5);
			//gr[mp[st2]][mp[st1]] = dist;
		}

		for(int k=1;k<KK;k++)
		{
			for(int i=1;i<KK;i++)
			{
				for(int j=1;j<KK;j++)
				{
					if(gr[i][j]>gr[i][k]+gr[k][j])
						gr[i][j] = gr[i][k]+gr[k][j];
				}
			}
		}

		bool f = true;
		while(Q--)
		{
			cin>>st1>>st2;
			if(f)
			{
				if(kase!=1)
				cout<<"\n";
				cout<<"Case #"<<kase++<<"\n";
				f=false;
			}
			if(gr[mp[st1]][mp[st2]]>=INF)
			cout<<"no route exists\n";
			else
			{
				/*long long d = floor(gr[mp[st1]][mp[st2]]);
				if(gr[mp[st1]][mp[st2]]-.5 >=d)
				cout<<ceil(floor(gr[mp[st1]][mp[st2]]))<<" km\n";
				else
				cout<<floor(floor(gr[mp[st1]][mp[st2]]))<<" km\n";
				*/
				printf("%d km\n",gr[mp[st1]][mp[st2]]);
			}

		}
	}

	return 0;
}