Distance calculation in C

Question

The question asks to calculate the shortest distance between cities. It was given the geographical coordinate of each region.

The right way out would be:
1646.3
189.9

My exit showed incorrect value in the second calculation:
1646.3
181.1

Link to the URI problem: https://www.urionlinejudge.com.br/judge/pt/problems/view/1270

Code:

#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <math.h>

#define INFINITO 100000000

struct cidade {
    char nome[15];
    int numRoteadores;
    int *coord_x;
    int *coord_y;
};

typedef struct cidade *Cidade;

Cidade newCidade(char nome[15], int numRoteadores) {  
    Cidade cidade = (Cidade) malloc(sizeof *cidade);  
    strcpy(cidade->nome, nome);  
    cidade->numRoteadores = numRoteadores;  
    cidade->coord_x = (int *) malloc(numRoteadores * sizeof(int));  
    cidade->coord_y = (int *) malloc(numRoteadores * sizeof(int));  

    return cidade;  
}  

int main() {
    int numCidades = -1;

    while(numCidades != 0){
        scanf("%d", &numCidades);

        if(numCidades >= 1 && numCidades <= 1000) {
            Cidade cidades[numCidades];
            char nomCidade;
            int numRoteadores;

            for(int i = 0; i < numCidades; i++){
                char nome[15];
                int numRoteadores;

                scanf("%s", nome);
                scanf("%d", &numRoteadores);

                cidades[i] = newCidade(nome, numRoteadores);

                for(int j = 0; j < numRoteadores; j++){
                    int coord_x, coord_y;

                    scanf("%d", &coord_x);
                    scanf("%d", &coord_y);

                    cidades[i]->coord_x[j] = coord_x;
                    cidades[i]->coord_y[j] = coord_y;
                }
            }

            float distTotal = 0;
            for(int i = 0; i < numCidades - 1; i++){
                char nome1[15];
                char nome2[15];
                Cidade cidade1;
                Cidade cidade2;

                scanf("%s", nome1);
                scanf("%s", nome2);

                int j = 0;
                int achou = 0;
                while(achou < 2){
                    if(strcmp(cidades[j]->nome, nome1) == 0 || strcmp(cidades[j]->nome, nome2) == 0){
                        if(achou == 0){
                            cidade1 = cidades[j];
                            achou++;
                        }else{
                            cidade2 = cidades[j];
                            achou++;
                        }

                    }
                    j++;
                }
                float dist = INFINITO;
                //Acredito que o problema esteja aqui, onde a distância é calculada
                for(int k = 0; k < cidade1->numRoteadores; k++){
                    for(int l = 0; l < cidade2->numRoteadores; l++){
                        float newDist = sqrt(pow((cidade2->coord_x[l] - cidade1->coord_x[k] ),2) + pow((cidade2->coord_y[l] - cidade1->coord_y[k]),2));
                        if(newDist < dist){
                            dist = newDist;
                        }
                    }
                }

                distTotal += dist;
            }

            printf("%.1f\n", distTotal);
        }
    }
}

Answer 1

You can use the Haversine’s formula to calculate the distance between two geographical coordinates:

Follows a code in C (tested) able to calculate the distance in kilometers between two geographical coordinates:

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

#define RAIO_GLOBO_TERRESTRE_KM  (6371)

double calcular_distancia( double th1, double ph1, double th2, double ph2 )
{
    double x = 0.0;
    double y = 0.0;
    double z = 0.0;

    ph1 -= ph2;
    ph1 *= M_PI / 180.0,
    th1 *= M_PI / 180.0,
    th2 *= M_PI / 180.0;

    z = sin(th1) - sin(th2);
    x = cos(ph1) * cos(th1) - cos(th2);
    y = sin(ph1) * cos(th1);

    return asin( sqrt( x * x + y * y + z * z) / 2.0) * 2.0 * RAIO_GLOBO_TERRESTRE_KM;
}


int main( void )
{
    double d = 0.0;

    d = calcular_distancia( -23.5489, -46.6388,    //Sao Paulo
                            -22.9035, -43.2096 );  //Rio de Janeiro

    printf("Sao Paulo x Rio de Janeiro: %.1f Km\n", d );


    d = calcular_distancia( -15.7801, -47.9292,    //Brasilia
                            -30.0277, -51.2287 );  //Porto Alegre

    printf("Brasilia x Porto Alegre: %.1f Km\n", d );

    return 0;
}

Compiling:

$ gcc -lm haversine.c -o haversine 

Exit:

Sao Paulo x Rio de Janeiro: 357.7 Km
Brasilia x Porto Alegre: 1619.6 Km

Answer 2

In the stretch:

float newDist = sqrt(pow((cidade2->coord_x[l] - cidade1->coord_x[k] ),2) + pow((cidade2->coord_y[l] - cidade1->coord_y[k]),2));

The coord variables are all integer but the result is being treated as float.

You will get in trouble here, either you work with all of them whole or you work with all of them float.

This type of conversion to C is absurdly problematic.