10075 - Airlines

All about problems in Volume 100. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

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

10075 - Airlines

Post by hj » Tue Dec 30, 2003 11:11 pm

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

Post by hj » Sat Jan 03, 2004 1:48 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[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
New poster
Posts: 23
Joined: Tue Sep 30, 2003 11:44 pm

Post by fpmc » Tue Jul 20, 2004 12:58 am

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

Post by rhsumon » Thu Jan 17, 2008 9:53 pm

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:

Post by suneast » Mon Jun 07, 2010 3:25 pm

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:

rein08
New poster
Posts: 3
Joined: Mon Jul 19, 2010 2:25 pm

Re: 10075 - Airlines

Post by rein08 » Thu Jul 22, 2010 1:57 pm

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

weber
New poster
Posts: 1
Joined: Thu Jul 29, 2010 10:22 am

Re: 10075 - Airlines

Post by weber » Thu Jul 29, 2010 10:27 am

remove after AC

User avatar
mahade hasan
Learning poster
Posts: 87
Joined: Thu Dec 15, 2011 3:08 pm
Location: University of Rajshahi,Bangladesh

Re: 10075 - Airlines

Post by mahade hasan » Sun Nov 04, 2012 10:12 pm

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

Post by brianfry713 » Tue Nov 06, 2012 11:12 pm

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

Post by amrondonp » Fri Apr 03, 2015 2:44 am

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.

Post Reply

Return to “Volume 100 (10000-10099)”