10075 - Airlines
Moderator: Board moderators
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.
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.
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]
[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]
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
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
Re:
I'm confused of this,too.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,.......
but until I notice this sentence
Code: Select all
Round the geographical distance between every pair of cities to the nearest integer.
![:wink:](./images/smilies/icon_wink.gif)
Re: 10075 - Airlines
Still got the WA.
I was asking some help from friends too.
Still,WA.
![:lol:](./images/smilies/icon_lol.gif)
I was asking some help from friends too.
Still,WA.
![:lol:](./images/smilies/icon_lol.gif)
Re: 10075 - Airlines
remove after AC
-
- Learning poster
- Posts: 87
- Joined: Thu Dec 15, 2011 3:08 pm
- Location: University of Rajshahi,Bangladesh
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!
need eyes to feel it!
-
- 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!
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 ![:)](./images/smilies/icon_smile.gif)
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.
![:)](./images/smilies/icon_smile.gif)
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.