Defibrillators – solution CodinGame en C
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
- Lire la position de l'utilisateurLisez longitude et latitude comme des chaînes, remplacez ',' par '.', convertissez en nombre à virgule flottante puis en radians.
- 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.
- 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.
- 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.
- Garder le minimumEn une seule passe, mémorisez la plus petite distance et le nom associé, puis affichez ce nom.
Complexité
O(N)O(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;
}
Defibrillators – Java
import java.util.*;
class Solution {
static double toRad(String s) {
return Math.toRadians(Double.parseDouble(s.replace(',', '.')));
}
public static void main(String args[]) {
Scanner in = new Scanner(System.in);
double lonA = toRad(in.next());
double latA = toRad(in.next());
int n = in.nextInt();
in.nextLine();
String bestName = "";
double bestDist = Double.POSITIVE_INFINITY;
for (int i = 0; i < n; i++) {
// limit -1 keeps empty fields (e.g. a missing phone number)
String[] f = in.nextLine().split(";", -1);
double lonB = toRad(f[4]);
double latB = toRad(f[5]);
double x = (lonB - lonA) * Math.cos((latA + latB) / 2);
double y = latB - latA;
double d = x * x + y * y;
if (d < bestDist) {
bestDist = d;
bestName = f[1];
}
}
System.out.println(bestName);
}
}
Defibrillators – Python 3
import math
def to_rad(s):
return math.radians(float(s.replace(",", ".")))
lon_a = to_rad(input())
lat_a = to_rad(input())
n = int(input())
best_name, best_dist = None, float("inf")
for _ in range(n):
fields = input().split(";")
# split first, convert only the coordinates: names can contain commas
lon_b, lat_b = to_rad(fields[4]), to_rad(fields[5])
x = (lon_b - lon_a) * math.cos((lat_a + lat_b) / 2)
y = lat_b - lat_a
d = x * x + y * y # the square root and the 6371 factor do not change the ranking
if d < best_dist:
best_dist, best_name = d, fields[1]
print(best_name)
Erreurs fréquentes
- Oublier la conversion en radianscos() attend des radians dans toutes les bibliothèques standard. Sans conversion le calcul est faux mais classe souvent les points correctement, ce qui masque le bug jusqu'au jour où deux défibrillateurs sont presque à égale distance.
- Lire '3,87' directement comme un nombrefloat('3,87') lève une erreur en Python, Double.parseDouble lance une exception en Java, et atof en C s'arrête silencieusement à la virgule et renvoie 3. Remplacez d'abord la virgule par un point.
- Perdre les champs videsstrtok en C fusionne les ';' consécutifs : un téléphone absent décale les coordonnées d'un champ. En Java, split(";", -1) est l'appel le plus sûr.
- Abîmer le nomRemplacer les virgules sur toute la ligne avant le découpage transforme « Hôtel de Ville, accueil » en « Hôtel de Ville. accueil », qui ne correspond plus à la sortie attendue.
- Lire mot par mot au lieu de ligne par ligneLes noms et adresses contiennent des espaces : Scanner.next() ou scanf("%s") découpent un défibrillateur en plusieurs morceaux. Lisez chaque défibrillateur comme une ligne complète.
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.