## 10075 - Airlines

Moderator: Board moderators

hj
New poster
Posts: 5
Joined: Sun May 25, 2003 11:56 am

### 10075 - Airlines

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.

hj
New poster
Posts: 5
Joined: Sun May 25, 2003 11:56 am
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;
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,c2;
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]

fpmc
New poster
Posts: 23
Joined: Tue Sep 30, 2003 11:44 pm
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

rhsumon
New poster
Posts: 48
Joined: Wed Aug 23, 2006 12:29 pm
Location: Dhaka
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,.......

suneast
New poster
Posts: 49
Joined: Sun Jan 17, 2010 6:25 am
Location: FZU
Contact:

### Re:

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... rein08
New poster
Posts: 3
Joined: Mon Jul 19, 2010 2:25 pm

### Re: 10075 - Airlines

Still got the WA.
I was asking some help from friends too.
Still,WA. weber
New poster
Posts: 1
Joined: Thu Jul 29, 2010 10:22 am

### Re: 10075 - Airlines

remove after AC

Learning poster
Posts: 87
Joined: Thu Dec 15, 2011 3:08 pm

### Re: 10075 - Airlines

cutttttttttttttttttt
Last edited by mahade hasan on Mon Nov 12, 2012 6:01 pm, edited 1 time in total.
we r surrounded by happiness
need eyes to feel it!

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 10075 - Airlines

Don't mix float and double in your Round function, try adding 0.5 and casting to an integer instead.
Check input and AC output for thousands of problems on uDebug!

amrondonp
New poster
Posts: 5
Joined: Fri Apr 03, 2015 2:29 am

### Re: 10075 - Airlines

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>