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

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

535 - Globetrotter

Post by 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
New poster
Posts: 1
Joined: Tue Aug 31, 2004 5:06 pm

535 Globetrotter

Post by 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
Learning poster
Posts: 53
Joined: Sat Jul 10, 2004 5:57 pm
Location: Shanghai China

535 help,i am so confused.

Post by 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
Experienced poster
Posts: 131
Joined: Sat Jul 17, 2004 4:09 am
Location: Lima, Per

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

Post by 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 :wink:
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

Post by Antonio Ocampo »

Please, help me!!!!!!!!!!!!! :cry:

myqbzi
New poster
Posts: 5
Joined: Thu Jul 22, 2004 3:12 pm
Location: Croatia

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

Post by Antonio Ocampo »

Please help me!!!!

CodeMaker
Experienced poster
Posts: 183
Joined: Thu Nov 11, 2004 12:35 pm
Location: AIUB, Bangladesh

Post by 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.
Jalal : AIUB SPARKS

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

Post by Antonio Ocampo »

Thanks for your reply CodeMaker :wink: 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 :D

CodeMaker
Experienced poster
Posts: 183
Joined: Thu Nov 11, 2004 12:35 pm
Location: AIUB, Bangladesh

Post by 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?
Jalal : AIUB SPARKS

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

Post by 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 :wink:

nnahas
New poster
Posts: 40
Joined: Mon Nov 01, 2004 7:56 pm

Post by nnahas »

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 :wink:
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
New poster
Posts: 5
Joined: Thu Jul 22, 2004 3:12 pm
Location: Croatia

Post by myqbzi »

Thx, nnahas! I finally got ACC. :D

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

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

Post by Antonio Ocampo »

Thx nnahas, at last I got AC too. :D

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

Hi oulongbin !!!

Post by 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...
Last edited by dovier_antonio on Fri Feb 03, 2012 9:53 am, edited 1 time in total.

Post Reply

Return to “Volume 5 (500-599)”