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
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 |
#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; } |