## 535 - Globetrotter

Moderator: Board moderators

lowai
New poster
Posts: 48
Joined: Mon Apr 29, 2002 1:26 pm

### 535 - Globetrotter

i think my formuale are exactly right.
any tricky there?
[pascal]
(* @JUDGE_ID: 13484EZ 535 Pascal "formula" *)
{D = R * ArcCos(cos(lat1)cos(lat2)[cos(long1)cos(long2) + sin(long1)sin(long2)] + sin(lat1)sin(lat2))
ArcCos(x) = ArcTan(sqrt(1 - sqr(x)) / x) }
const
maxcity = 1000;
R = 6378;
Pi = 3.141592653589793;
type
tcity = record
lat, long : real;
name : string;
end;
var
n : integer;
city : array[1..maxcity]of tcity;

function init : boolean;
var ch : char;
s : string;
begin
ch := #0;
s := '';
while (ch <> #26)and(ch <> '#')and(ch <> ' ')and(ch <> #9) do
begin s := s + ch; read(ch); end;
if s = '' then begin init := false; readln; exit; end;
inc(n);
city[n].name := s;
city[n].lat := city[n].lat * pi / 180;
city[n].long := city[n].long * pi / 180;
init := true;
end;

function getid(name : string) : integer;
var i : integer;
begin
for i := 1 to n do
if city.name = name then
begin getid := i; exit; end;
getid := 0;
end;

function sphericaldistance(i, j : integer) : real;
var q : real;
begin
q := cos(city.lat) * cos(city[j].lat) * cos(city.long - city[j].long) +
sin(city.lat) * sin(city[j].lat);
if q = 0 then q := Pi / 2 else
begin
q := sqrt (1 - sqr (q)) / q;
q := arctan(q);
if q < 0 then q := q + Pi;
end;
sphericaldistance := R * q;
end;

procedure main;
var s, name1, name2 : string;
i, c1, c2 : integer;
begin
i := pos(' ', s);
if i = 0 then i := pos(#9, s);
name1 := copy(s, 1, i - 1);
name2 := copy(s, i + 1, length(s) - i);
while (name1 <> '#') and (name2 <> '#') do
begin
writeln(name1, ' - ', name2);
c1 := getid(name1);
c2 := getid(name2);
if (c1 = 0) or (c2 = 0) then
writeln('Unknown')
else
writeln(sphericaldistance(c1, c2) : 0 : 0, ' km');
i := pos(' ', s);
if i = 0 then i := pos(#9, s);
name1 := copy(s, 1, i - 1);
name2 := copy(s, i + 1, length(s) - i);
end;
end;

begin
n := 0;
while init do;
main;
end.
[/pascal]

niebo077
New poster
Posts: 1
Joined: Tue Aug 31, 2004 5:06 pm

### 535 Globetrotter

I'm getting WA from the online judge. Anyone who have some more test cases or can help with with what's wrong? (I get the same result as the sample output)

[cpp]
#include <iostream>
#include <cmath>
#include <map>
#include <string>

#ifndef ONLINE_JUDGE
#include <fstream>
#endif

#define PI 3.141592653589793
#define R 6378.0

using namespace std;

struct Position {
double p_lat, p_long;
};

double sphericalDistance(Position& a, Position& b) {
return R * acos(sin(a.p_long)*sin(b.p_long) +
cos(a.p_long)*cos(b.p_long)*cos(a.p_lat)*cos(b.p_lat) +
cos(a.p_long)*cos(b.p_long)*sin(a.p_lat)*sin(b.p_lat));
}

double deg2rand(double deg) {
return (deg*PI)/180;
}

int main() {

#ifndef ONLINE_JUDGE
ifstream in("535Globetrotter.in");
assert(in);
#else
istream& in = cin;
#endif

map<string, Position> citylist;
while(in.peek() != '#') {
string city;
Position p;
double p_long, p_lat;

in >> city;
in >> p_long >> p_lat;

p.p_long = deg2rand(p_long);
p.p_lat = deg2rand(p_lat);

citylist[city] = p;
in >> ws;
}
in.get(); //eat #

/*
for(map<string, Position>::const_iterator iter = citylist.begin();
iter != citylist.end(); ++iter)
cout << iter->first << ": "
<< iter->second.p_long << " "
<< iter->second.p_lat << endl;
*/

while(in.peek() != '#') {
string city1, city2;
Position a, b;
map<string, Position>::const_iterator iter;

in >> city1 >> city2 >> ws;
cout << city1 << " - " << city2 << endl;

iter = citylist.find(city1);
if(iter == citylist.end()) {
cout << "Unknown" << endl;
continue;
} else {
a = (iter)->second;
}

iter = citylist.find(city2);
if(iter == citylist.end()) {
cout << "Unknown" << endl;
continue;
} else {
b = (iter)->second;
}

cout << static_cast<int>(sphericalDistance(a,b)+0.5) << " km" << endl;

}

#ifndef ONLINE_JUDGE
in.close();
#endif

return 0;

}

[/cpp]

oulongbin
Learning poster
Posts: 53
Joined: Sat Jul 10, 2004 5:57 pm
Location: Shanghai China

### 535 help,i am so confused.

[cpp]
#include <iostream>
using namespace std;
#include <cstring>
#include <cmath>
#include <cstdio>
double r=6378.0;
double spherical_distance(double p_lat,double p_long,double q_lat,double q_long)
{
return 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;
}

int main()
{
char name;
char a,b;
double latitude;
double longitude;
double p_lat,p_long,q_lat,q_long;
double distance;
long d;
int i;
int ii,jj;
double pi=2.0*acos(0);
i=0;
while(cin>>name)
{
if(!strcmp(name,"#"))
break;
cin>>latitude>>longitude;
i++;
}
while(cin>>a>>b)
{
if(!strcmp(a,"#")&&!strcmp(b,"#"))
break;
for(ii=0;ii<i;ii++)
{
if(!strcmp(a,name[ii]))
{
p_lat=latitude[ii]*(pi/180.0);
p_long=longitude[ii]*(pi/180.0);
break;
}
}
for(jj=0;jj<i;jj++)
{
if(!strcmp(b,name[jj]))
{
q_lat=latitude[jj]*(pi/180.0);
q_long=longitude[jj]*(pi/180.0);
break;
}
}
if(ii!=i&&jj!=i)
{
distance=spherical_distance(p_lat,p_long,q_lat,q_long);
if(distance-int(distance)<0.5)
d=int(distance);
else
d=int(distance+0.5);
cout<<a<<" - "<<b<<endl;
cout<<d<<" km"<<endl;
}
else
{
cout<<a<<" - "<<b<<endl;
cout<<"Unknown"<<endl;
}
}
return 0;
}
[/cpp]

Antonio Ocampo
Experienced poster
Posts: 131
Joined: Sat Jul 17, 2004 4:09 am
Location: Lima, Per

### 535 Globetrotter I need help!!!!!!!!!!

I think what my code is OK but I don't know why I got WA. Please, could you tell me where is the mistake ?

Code: Select all

``````Cut after AC :)
``````

Thanks in advance Last edited by Antonio Ocampo on Fri Jan 21, 2005 4:38 am, edited 1 time in total.

Antonio Ocampo
Experienced poster
Posts: 131
Joined: Sat Jul 17, 2004 4:09 am
Location: Lima, Per
Please, help me!!!!!!!!!!!!! myqbzi
New poster
Posts: 5
Joined: Thu Jul 22, 2004 3:12 pm
Location: Croatia
I've got the same problem. I'm getting WA all the time, but all solutions for given test cases are correct. Someone please help. Here is my code:

Code: Select all

``````   Removed... I got ACC. :)
``````
Last edited by myqbzi on Thu Jan 20, 2005 11:38 pm, edited 1 time in total.

Antonio Ocampo
Experienced poster
Posts: 131
Joined: Sat Jul 17, 2004 4:09 am
Location: Lima, Per

CodeMaker
Experienced poster
Posts: 183
Joined: Thu Nov 11, 2004 12:35 pm
Hi guys, I also got WA for this problem and this problem is all about precision errors.

myqbzi, there is a point for you: the problem states that you have to convert the value of your calculation to nearest integer value.

to do that you must add 0.5 with your calculated value and then cut off the floating part.

example: 4.7 will be 5 as 4.7+0.5=5.2
but : 4.3 will be 4 as 4.3+0.5=4.8

but the problem is if you use this in your code then some of the sample output will not match(I have the same problem, but adding 0.5 is correct)
so the problem is somewhere else, you are getting right output because the problem setter has fooled you. but the real data set will catch you if you dont use the addition.

main problem is in the formula we are using. there is a way that we have to take.so start thinking about it how can the miscalculation can be avoided.

and for Antonio Ocampo: i did not see you to use "setprecision" function, i think it is a time to give it a try. i will try it now, if anyone of you get acc, please remember to notice it.
Jalal : AIUB SPARKS

Antonio Ocampo
Experienced poster
Posts: 131
Joined: Sat Jul 17, 2004 4:09 am
Location: Lima, Per
Thanks for your reply CodeMaker One more question, why I must use "setprecision"???

According to the statement:
...print a line saying ``x km" where x is replaced by the geographical distance (in km) between the two cities, rounded to the nearest integer.
I have used:

Code: Select all

``````cout<<long(distancia(lat1*pi/180.0,lon1*pi/180.0,lat2*pi/180.0,lon2*pi/180.0)+0.5)<<" km\n";
``````
It converts the value of "distancia" to nearest integer value. (Also I added 0.5)

Thanks in advance CodeMaker
Experienced poster
Posts: 183
Joined: Thu Nov 11, 2004 12:35 pm
Everything looks ok in your code and I also have tried with many things.
But could not get AC so I wanted to use the setprecision function to check is this all about percision error....but now i think the formula is not working, is there any other formula?
Jalal : AIUB SPARKS

Antonio Ocampo
Experienced poster
Posts: 131
Joined: Sat Jul 17, 2004 4:09 am
Location: Lima, Per
Well, I've used this formula in another problem and it really works!!! Please someone who have got AC, send me some I/O.

Thx in advance nnahas
New poster
Posts: 40
Joined: Mon Nov 01, 2004 7:56 pm
Antonio Ocampo wrote:Well, I've used this formula in another problem and it really works!!! Please someone who have got AC, send me some I/O.

Thx in advance I got AC, and there's several problem with your code at the top of this page .

1)If you enter a query with the 2 cities having the same name but not in the list your program will return 0 km when it should return Unknown.
2)If there is a query of the form "# Paris" you should return Unknown not end the program.
3)If the city list is empty, meaning the first line consists just of one #
4)same thing if the list of queries is empty.
5)Your formula for distance while correct , suffers from precision problems. Use the Haversine formula instead. see
http://mathforum.org/library/drmath/view/51879.html

myqbzi
New poster
Posts: 5
Joined: Thu Jul 22, 2004 3:12 pm
Location: Croatia
Thx, nnahas! I finally got ACC. I've just changed my formula in original code to this Haversine. Thanks a lot...

Antonio Ocampo
Experienced poster
Posts: 131
Joined: Sat Jul 17, 2004 4:09 am
Location: Lima, Per
Thx nnahas, at last I got AC too. dovier_antonio
New poster
Posts: 47
Joined: Fri Feb 18, 2005 5:00 am
Location: Havana, Cuba

### Hi oulongbin !!!

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;
}

Look out your formula... it seems to be wrong...
Last edited by dovier_antonio on Fri Feb 03, 2012 9:53 am, edited 1 time in total.