535 - Globetrotter

[lowai]

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[30];
end;
var
n : integer;
city : array[1..maxcity]of tcity;

function init : boolean;
var ch : char;
s : string;
begin
ch := #0;
s := '';
read(ch);
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;
readln(city[n].lat, city[n].long);
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
readln(s);
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');
readln(s);
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]

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

//Read in citylist:
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;
*/

//Read and process querylist:
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]

i don't know why i always got WA.please help me ,thank you !
[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[110][50];
char a[50],b[50];
double latitude[110];
double longitude[110];
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]

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

[Antonio Ocampo]

Please, help me!!!!!!!!!!!!!

[myqbzi]

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. :)

[Antonio Ocampo]

Please help me!!!!

[CodeMaker]

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.

[Antonio Ocampo]

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]

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?

[Antonio Ocampo]

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]

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 #
your program will return a wrong answer.
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]

Thx, nnahas! I finally got ACC.

I've just changed my formula in original code to this Haversine. Thanks a lot...
It's all about precisions...

[Antonio Ocampo]

Thx nnahas, at last I got AC too.

[dovier_antonio]

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