Coding Solution

Defibrillators – solution CodinGame en C

Facilestring parsingdistance formulalinear searchMis à jour le
Réponse courte

Lisez la longitude et la latitude de l'utilisateur en remplaçant la virgule par un point, puis découpez chaque ligne de défibrillateur sur ';'. Les champs 4 et 5 donnent la longitude et la latitude : convertissez tout en radians, calculez x = dLon * cos((latA + latB) / 2) et y = dLat, et gardez le nom (champ 1) dont x² + y² est le plus petit.

L'énoncé

Vous connaissez votre position (longitude et latitude en degrés) et une liste de N défibrillateurs de Montpellier. Chaque ligne contient un identifiant, un nom, une adresse, un téléphone, une longitude et une latitude, séparés par des points-virgules. Il faut afficher le nom du défibrillateur le plus proche.

Les nombres utilisent la virgule décimale à la française (3,879483), certains champs peuvent être vides, et la distance se calcule avec l'approximation plane fournie dans l'énoncé, qui attend des angles en radians. Un seul nom est attendu en sortie.

La démarche, étape par étape

  1. Lire la position de l'utilisateurLisez longitude et latitude comme des chaînes, remplacez ',' par '.', convertissez en nombre à virgule flottante puis en radians.
  2. Découper chaque ligneSéparez sur ';' en conservant les champs vides : le téléphone manque souvent, ce qui donne deux points-virgules consécutifs. Le champ 1 est le nom, le 4 la longitude, le 5 la latitude.
  3. Ne convertir que les coordonnéesFaites le remplacement virgule -> point uniquement sur les deux champs numériques, pas sur toute la ligne, pour qu'un nom contenant une virgule reste intact.
  4. Calculer la distancex = (lonB - lonA) * cos((latA + latB) / 2) et y = latB - latA. Comme on ne fait que comparer, x² + y² suffit : la racine carrée et le rayon 6371 ne changent pas l'ordre.
  5. Garder le minimumEn une seule passe, mémorisez la plus petite distance et le nom associé, puis affichez ce nom.

Complexité

TempsO(N)
MémoireO(1)

Chaque ligne est analysée et comparée une seule fois, et on ne garde que le meilleur candidat courant : la mémoire ne dépend pas de N (hors tampon de lecture).

Code de la solution

Defibrillators – C

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

/* Converts "3,879483" to radians (the input uses a decimal comma) */
static double toRad(char *s) {
    for (char *p = s; *p; p++) if (*p == ',') *p = '.';
    return atof(s) * M_PI / 180.0;
}

int main(void) {
    char buf[64];
    scanf("%63s", buf); double lonA = toRad(buf);
    scanf("%63s", buf); double latA = toRad(buf);
    int n;
    scanf("%d", &n);
    fgetc(stdin);

    char line[1024], best[256] = "";
    double bestDist = DBL_MAX;
    for (int i = 0; i < n; i++) {
        if (!fgets(line, sizeof line, stdin)) break;
        line[strcspn(line, "\r\n")] = '\0';
        /* split on ';' by hand: strtok would merge empty fields */
        char *field[6] = {0};
        char *p = line;
        for (int k = 0; k < 6 && p; k++) {
            field[k] = p;
            p = strchr(p, ';');
            if (p) *p++ = '\0';
        }
        if (!field[5]) continue;
        double lonB = toRad(field[4]);
        double latB = toRad(field[5]);
        double x = (lonB - lonA) * cos((latA + latB) / 2);
        double y = latB - latA;
        double d = x * x + y * y;
        if (d < bestDist) {
            bestDist = d;
            strncpy(best, field[1], sizeof best - 1);
        }
    }
    puts(best);
    return 0;
}

Erreurs fréquentes

Pour aller plus loin

La formule de l'énoncé est l'approximation équirectangulaire : à une latitude donnée, un degré de longitude est plus court qu'un degré de latitude d'un facteur cos(latitude), d'où la correction de x avant Pythagore. À l'échelle d'une ville, l'erreur est inférieure au mètre : la formule de haversine n'apporte rien ici. Conséquences pratiques : on peut supprimer la racine et le facteur 6371, fonctions croissantes, et même calculer cos(latitude) une seule fois puisque tous les points sont à Montpellier. C'est aussi pour cela que le code en degrés passe quand même les tests : un mauvais coefficient sur x déforme la métrique mais inverse rarement le classement. Pour vous en convaincre, fabriquez un test avec deux points presque équidistants.

Questions fréquentes

Faut-il utiliser la formule de haversine ?

Non. L'énoncé fournit l'approximation équirectangulaire, quasi identique à haversine sur une ville. Utiliser la formule donnée garantit en plus le même classement que la solution de référence.

Pourquoi mon programme affiche-t-il le mauvais défibrillateur ?

Le plus souvent : des degrés passés à cos() au lieu de radians, une virgule restée dans un nombre (atof('3,87') vaut 3), ou des champs décalés parce qu'un téléphone vide a disparu au découpage.

Peut-on se passer de la racine carrée ?

Oui. Comparer x² + y² donne le même ordre que comparer les vraies distances, car la racine et la multiplication par le rayon terrestre sont croissantes.

Puzzles similaires

★ 5,0 · 16 avis · 928 utilisateurs Ajouter à Chrome