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

[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