10075 - Airlines

[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.

[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]

[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

[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,.......

[suneast]

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]

Still got the WA.
I was asking some help from friends too.
Still,WA.

[weber]

remove after AC

[mahade hasan]

cutttttttttttttttttt

[brianfry713]

Don't mix float and double in your Round function, try adding 0.5 and casting to an integer instead.

[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.