Page 1 of 1

10075 - Airlines

Posted: Tue Dec 30, 2003 11:11 pm
by hj
hi, i'am trying to solve this magic problem. I calculate distance between two cities using following formula:
d=acos(cos(lat1)*cos(lat2)*cos(lon1-lon2)+sin(lat1)*sin(lat2))*R,
lat_i and lon_i are latitude and longitude. Then use floyd to calculate minimal disctance.
I've got correct answers for sample input except case #2 (distance between Dhaka and Hong_Kong, first in query) my output is 19653, but sample output is 19654. I've calculated distance between two cites in many ways (e.g using cartesian coordinates) but always got
19653.11244303 for this test case. Could sombody help me ?. Give me some input/output
Thanks
HJ.

Posted: Sat Jan 03, 2004 1:48 am
by hj
I post my code to make my problem clear. I still got round errors with this code. Any help ?
[cpp]
#include <iostream>
#include <cstdlib>
#include <cmath>
#include <cstring>

using namespace std;
#define MAX 320
#define MAXC 150

long double R=6378.0;
long double mypi=3.141592653589793;

long double INFTY=1000000000.0;
long double t[MAX][MAX];

struct city{
char name[50];
long double lt,ln;

} tCity[MAXC];


int index(char *s){
int i=0;
while (strcmp(tCity.name,s)) ++i;
return i;
}


void out(int N){
for (int i=0;i<N;++i){
for(int j=0;j<N;++j) cout<< t[j]<<" ";
cout << endl;
}
}


int main(){
unsigned int N, M, Q;
int cas;


char c1[50],c2[50];
cas=0;
cout.setf(ios::fixed);
cout.precision(3);
cin >> N >> M >> Q;
while (N || M || Q){
++cas;
for(int i=0;i<N;++i)
for(int j=0;j<N;++j)
t[j]= (i==j) ? 0.0 : INFTY;

for(int i=0;i<N;++i){
long double lt,ln;
cin >> tCity.name>> lt >> ln;
tCity.lt=(lt*mypi)/180.0;
tCity.ln=(ln*mypi)/180.0;
}

for(int i=0;i<M;++i){
cin >> c1 >> c2;
int i1=index(c1);
int i2=index(c2);
long double
tmp=acos(sin(tCity[i1].lt)*sin(tCity[i2].lt)+cos(tCity[i1].lt)*cos(tCity[i2].lt)*cos(tCity[i1].ln-tCity[i2].ln))*R;
if(t[i1][i2]>tmp) t[i1][i2]=tmp;

}


for(int k=0;k<N;++k)
for(int i=0;i<N;++i)
for(int j=0;j<N;++j)
if(t[k]+t[k][j]<t[j]) t[j]=t[k]+t[k][j];

cout<< "Case #"<<cas<<endl;
for(int i=0;i<Q;++i){
cin>> c1 >> c2;
int i1=index(c1);
int i2=index(c2);
if (t[i1][i2]==INFTY) cout<<"no route exists"<<endl;
else
cout<<t[i1][i2]<<" km"<<endl;
}

cout<<endl ;
cin >> N >> M >> Q;
}
return 0;
}
[/cpp]

Posted: Tue Jul 20, 2004 12:58 am
by fpmc
When calculating distance, round the distance to integer for every edge BEFORE adding them.

For example,
CityA -> CityB, 12.3km
CityB -> CityC, 7.4km

Then CityA -> CityC will be round(12.3) + round(7.4) = 12+7 = 19, and NOT round(12.3+7.4) = round(19.7) = 20

This would just mean that you should change your 't' matrix to int and do the relevant modifications to your code.

Frank

Posted: Thu Jan 17, 2008 9:53 pm
by rhsumon
I worked according to ur suggetion
But i got for the case 2
Dhaka Hong kong
19652 km where the ans would be 19654

Plz describe ur idea brifly...... to understood us well................
plz i'm boaring .... now ... now i'm helpless,.......

Re:

Posted: Mon Jun 07, 2010 3:25 pm
by suneast
rhsumon wrote:I worked according to ur suggetion
But i got for the case 2
Dhaka Hong kong
19652 km where the ans would be 19654

Plz describe ur idea brifly...... to understood us well................
plz i'm boaring .... now ... now i'm helpless,.......
I'm confused of this,too.
but until I notice this sentence

Code: Select all

Round the geographical distance between every pair of cities to the nearest integer.
Hope I'm help to othes... :wink:

Re: 10075 - Airlines

Posted: Thu Jul 22, 2010 1:57 pm
by rein08
Still got the WA.
I was asking some help from friends too.
Still,WA.
:lol:

Re: 10075 - Airlines

Posted: Thu Jul 29, 2010 10:27 am
by weber
remove after AC

Re: 10075 - Airlines

Posted: Sun Nov 04, 2012 10:12 pm
by mahade hasan
cutttttttttttttttttt

Re: 10075 - Airlines

Posted: Tue Nov 06, 2012 11:12 pm
by brianfry713
Don't mix float and double in your Round function, try adding 0.5 and casting to an integer instead.

Re: 10075 - Airlines

Posted: Fri Apr 03, 2015 2:44 am
by amrondonp
Yes, you need to round the distance BEFORE sum them. In other words, when you compute the distance between city A and B, store it as the nearest integer. Then apply the algorithm you want- I used C++11 and Floyd I got AC thanks to this forum :)

Also, I applied the formula that comes directly from linear algebra and geograhical coordinates which tells you that

Let a1,a2 the longitude of city One and Two
Let b1,b2 the latitude of city One and Two

If you apply geographical coordinates in order to get those vectors, you'll be able to compute the cosine of the angle <a> between them and then.

Since u =( Rcos(a1)cos(b1) , Rcos(b1)sin(a1), Rsin(b1) )
and v = ( Rcos(a2)cos(b2) , Rcos(b2)sin(a2), Rsin(b2) )

then u*v = |u||v|cos<a>

u*v = R^2cos<a> (two vectors have length R)
cos<a> = u*v / R^2

Let's compute u*v

u*v = R^2 ( cos(a1)cos(b1)cos(a2)cos(b2) + cos(b1)sin(a1)cos(b2)sin(a2) + sin(b1)sin(b2) )

u*v = R^2( cos(a1-a2) * cos(b1)cos(b2) + sin(b1)(b2) ) //Since that cos<b>cos<a> + sin<b>sin<a> = cos(a-b)

so

cos<a> = cos(a1-a2) * cos(b1)cos(b2) + sin(b1)(b2)

then <a> = acos ( cos(a1-a2) * cos(b1)cos(b2) + sin(b1)(b2) )

DISTANCE: d = R<a>

Hope this will help you.