## 535 - Globetrotter

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

Moderator: Board moderators

dovier_antonio
New poster
Posts: 47
Joined: Fri Feb 18, 2005 5:00 am
Location: Havana, Cuba

### Hi niebo077 !!!

AC source code removed...
Last edited by dovier_antonio on Fri Feb 03, 2012 9:53 am, edited 1 time in total.

dovier_antonio
New poster
Posts: 47
Joined: Fri Feb 18, 2005 5:00 am
Location: Havana, Cuba

### Hi lowai !!!

Look out this formula:

double spherical_distance(double lat1,double lon1,double lat2,double lon2) {

double dlon = lon2 - lon1;
double dlat = lat2 - lat1;
double a = pow((sin(dlat/2)),2) + cos(lat1) * cos(lat2) * pow(sin(dlon/2), 2);
double c = 2 * atan2(sqrt(a), sqrt(1-a));
double d = r * c;

return d;
}

I think that you have a problem with the precision.
Last edited by dovier_antonio on Fri Feb 03, 2012 9:51 am, edited 1 time in total.

Staryin
New poster
Posts: 12
Joined: Fri Dec 16, 2005 4:22 pm
Location: shanghai/china
Contact:

### 535 !WHY WA??!! I HAVE TRY ALL THE TEST DATA!!BUT...

Code: Select all

/*
spherical_distance(p_lat,p_long,q_lat,q_long) =
acos( sin(p_lat) * sin(q_lat) +
cos(p_lat) * cos(q_lat) * cos(p_long) * cos(q_long) +
cos(p_lat) * cos(q_lat) * sin(p_long) * sin(q_long)
) * r
*/

#include<iostream>
#include<cstring>
#include<cmath>
#include<cstdio>

#define pi 3.141592653589793
#define R 6378
using namespace std;

char city[100][30],a[30],b[30];
double la[100],lo[100],sla,slo,ela,elo,ans;
int i,j,citynum;
double dis(double a,double b,double c,double d)
{

return 	acos((sin(a)*sin(c)+cos(a)*cos(c)*cos(b)*cos(d)+
cos(a)*cos(c)*sin(b)*sin(d))) *R;

}
void solve()
{
if(strcmp(a,b)==0)
{
printf("%s - %s\n",a,b);
cout<<"0 km"<<endl;
return;
}

for(i=0;i<citynum && strcmp(a,city[i]);i++);
for(j=0;j<citynum && strcmp(b,city[j]);j++);

if(i==citynum || j==citynum)
{
printf("%s - %s\n",a,b);
cout<<"Unknown"<<endl;
return;
}

sla=la[i];slo=lo[i];ela=la[j];elo=lo[j];

ans=(int)(dis(sla*pi/180,slo*pi/180,ela*pi/180,elo*pi/180)+0.5);
printf("%s - %s\n",a,b);
printf("%.0f km\n",ans);
//printf("%d km\n",ans);

}

{
i=0;
while(1)
{
cin>>city[i];
if(city[i][0]=='#')
break;

cin>>la[i]>>lo[i];
i++;
}

citynum=i;
while(1)
{
cin>>a>>b;
if(a[0]=='#' && b[0]=='#')
break;

solve();

}

}

int main()
{
return 0;
}

Ashkankhan
New poster
Posts: 12
Joined: Wed Oct 13, 2004 10:14 am
Location: Teh
Contact:

### 535 : Globetrotter

What's wrong with my code?

Code: Select all

#include <stdio.h>
#include <string.h>
#include <math.h>
double pi=3.141592653589793;
double r=6378;
struct city
{
char name[32];
double x;
double y;
int l;
};
city a[102];
char p[102];
char q[102];
main()
{
int i=0,lp,lq,j,f,g,h,c;
double d;
scanf("%s",&a[i].name);
a[i].l=strlen(a[i].name);
while(a[i].name[0]!='#')
{
scanf("%lf%lf",&a[i].x,&a[i].y);
//printf("%s\t%lf\t%lf\n",a[i].name,a[i].x,a[i].y);
i++;
scanf("%s",&a[i]);
a[i].l=strlen(a[i].name);
}
scanf("%s%s",&p,&q);
while(p[0]!='#' || q[0]!='#')
{
lp=strlen(p);
lq=strlen(q);
if(i==0)
f=0;
for(j=0;j<i;j++)
{
f=1;
if(lp==a[j].l)
{
for(h=0;h<strlen(a[j].name);h++)
{
if(a[j].name[h]!=p[h])
{
f=0;
break;
}
}
if(f)
break;
}
else
f=0;
}
if(!f)
{
printf("%s - %s\nUnknown\n",p,q);
}
else
{
for(g=0;g<i;g++)
{
f=1;
if(lq==a[g].l)
{
for(h=0;h<strlen(a[g].name);h++)
{
if(a[g].name[h]!=q[h])
{
f=0;
break;
}
}
if(f)
break;
}
else
f=0;
}
if(!f)
{
printf("%s - %s\nUnknown\n",p,q);
}
else
{
d=acos(sin(a[j].x*pi/180)*sin(a[g].x*pi/180)+cos(a[j].x*pi/180)*cos(a[g].x*pi/180)*(cos(a[j].y*pi/180)*cos(a[g].y*pi/180)+sin(a[j].y*pi/180)*sin(a[g].y*pi/180)))*r;
if(d==0)
printf("%s - %s\nUnknown\n",p,q);
else
{
c=(int)d;
if(d-c>.5)
c++;
printf("%s - %s\n%d km\n",a[j].name,a[g].name,c);
}
}
}
scanf("%s%s",&p,&q);
}
return 0;
}

emotional blind
A great helper
Posts: 383
Joined: Mon Oct 18, 2004 8:25 am
Contact:
I need some i/o for this problem,
WA and WA .. i read all post already but cant overcome
Thanks.

5olio
New poster
Posts: 4
Joined: Wed Jun 18, 2008 1:23 pm

### Re: 535 Globetrotter I need help!!!!!!!!!!

emotional blind wrote:I need some i/o for this problem,
WA and WA .. i read all post already but cant overcome
Thanks.
I Have The Same Problem.

Code: Select all

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <math.h>

using namespace std;

struct City
{
string Name;
long double Latitude, Longitude;
};

vector<City> Citys;

int DistanceBetween(int City1, int City2)
{
long double ConvertToRadus = (3.141592653589793 / 180.0);

long double Latitude1 = Citys[City1].Latitude * ConvertToRadus;
long double Longitude1 = Citys[City1].Longitude * ConvertToRadus;
long double Latitude2 = Citys[City2].Latitude * ConvertToRadus;
long double Longitude2 = Citys[City2].Longitude * ConvertToRadus;

long double Distance = acos( sin(Latitude1) * sin(Latitude2) +
cos(Latitude1) * cos(Latitude2) * cos(Longitude1) * cos(Longitude2) +
cos(Latitude1) * cos(Latitude2) * sin(Longitude1) * sin(Longitude2)
) * 6378.0; // 6378 = R Of Earth

return int(Distance + 0.5);
}

int isAvalible(string CityName)
{
for(int i = 0; i < Citys.size(); i ++)
{
if(CityName == Citys[i].Name)
return i;
}

return -1;
}

int main()
{
freopen("ACM.in", "r", stdin);

City Temp;

while(cin >> Temp.Name)
{
if(Temp.Name == "#")
break;
cin >> Temp.Latitude >> Temp.Longitude;

Citys.push_back(Temp);
}

string FirstCityName, SecondCityName;

while(cin >> FirstCityName >> SecondCityName)
{
if(FirstCityName == "#" && SecondCityName == "#")
break;

cout << FirstCityName << " - " << SecondCityName << endl;

int City1 = isAvalible(FirstCityName);
int City2 = isAvalible(SecondCityName);

if(City1 != -1 && City2 != -1)
cout << DistanceBetween(City1, City2) << " km" << endl;

else
cout << "Unknown"<< endl;
}

return 0;
}
Thanks