535 - Globetrotter

[dovier_antonio]

AC source code removed...

[dovier_antonio]

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.

[Staryin]

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

void read()
{
	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()
{
	read();
	return 0;	
}

[Ashkankhan]

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]

I need some i/o for this problem,
WA and WA .. i read all post already but cant overcome
Thanks.

[5olio]

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