Defibrillators – CodinGame solution in C
Parse the user's longitude and latitude (replacing the decimal comma with a dot), then for each defibrillator split the line on ';', read fields 4 and 5 as longitude and latitude, convert everything to radians and compute the equirectangular distance x = dLon * cos((latA + latB) / 2), y = dLat, d = sqrt(x^2 + y^2). Keep the name (field 1) of the smallest distance and print it.
The problem
You are given your position as a longitude and a latitude in degrees, followed by N lines that each describe a defibrillator in Montpellier: an id, a name, an address, a phone number, a longitude and a latitude, separated by semicolons. You must print the name of the defibrillator closest to you.
The numbers use a French-style decimal comma (3,879483), some fields may be empty, and the distance is computed with the flat-earth approximation given in the puzzle, which needs angles in radians. Only one name is expected on the output.
Approach, step by step
- Read the user positionRead the longitude and latitude as strings, replace the ',' with '.', parse them as floating-point numbers and convert them to radians.
- Split each defibrillator lineSplit on ';' while keeping empty fields: the phone number is often missing, so you get two consecutive semicolons. Field 1 is the name, field 4 the longitude, field 5 the latitude.
- Convert only the coordinatesApply the comma-to-dot replacement on the two coordinate fields only, not on the whole line, so a name that contains a comma is printed unchanged.
- Compute the distanceUse x = (lonB - lonA) * cos((latA + latB) / 2) and y = latB - latA. Since you only compare distances, x^2 + y^2 is enough: the square root and the Earth radius 6371 do not change the order.
- Keep the minimumTrack the smallest distance seen and the name attached to it in a single pass, then print that name.
Complexity
O(N)O(1)Each line is parsed and compared once and only the current best is stored, so memory does not depend on N (apart from the line buffer).
Solution code
Bug fixed in this version: All three original versions plug degrees straight into cos(), while the distance formula expects radians, so the horizontal term is weighted by cos(43.6 rad) instead of cos(43.6 degrees). It happens to pass the CodinGame tests, but it can pick the wrong defibrillator when two candidates are almost tied. The Java and Python versions also replace commas in the whole line, which would alter a name containing a comma, and the C parser walks past the end of the buffer if a coordinate has no decimal comma. Corrected versions for all three languages are provided.
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)
Common mistakes
- Forgetting the degrees-to-radians conversioncos() in every standard library takes radians. Without the conversion the result is wrong but often still ranks correctly, which hides the bug until a test where two defibrillators are close to each other.
- Parsing '3,87' as a number directlyfloat('3,87') raises an error in Python and Double.parseDouble throws in Java, while atof in C silently stops at the comma and returns 3. Replace the comma with a dot first.
- Losing empty fields when splittingstrtok in C merges consecutive ';', so a missing phone number shifts the coordinates by one field. In Java, split(";") keeps inner empty fields but drops trailing ones; split(";", -1) is the safe call.
- Corrupting the nameReplacing commas on the whole line before splitting changes a name such as 'Hotel de Ville, accueil' into 'Hotel de Ville. accueil', which no longer matches the expected output.
- Reading tokens instead of linesNames and addresses contain spaces, so reading with Scanner.next() or scanf("%s") splits a defibrillator across several reads. Read each defibrillator as a full line.
Going further
The formula from the statement is the equirectangular approximation: near a given latitude, one degree of longitude is shorter than one degree of latitude by a factor cos(latitude), so the code shrinks the longitude difference before applying Pythagoras. At the scale of a city this is accurate to well under a metre, so the haversine formula brings nothing here. Two practical consequences: you can drop the sqrt and the 6371 factor because they are monotonic, and since every point lies in Montpellier you could even compute cos(latitude) once for the user and reuse it. The reason the degree-based code still passes is precisely this monotonic structure: a wrong constant multiplier on x distorts the metric but rarely flips the ranking, so validate with a hand-built test of two near-equidistant points if you want to be sure.
FAQ
Do I need the haversine formula for Defibrillators?
No. The puzzle gives the equirectangular approximation, and over a city-sized area it is practically identical to haversine. Using the given formula also guarantees you rank points exactly like the reference solution.
Why does my solution print the wrong defibrillator?
The usual causes are degrees passed to cos() instead of radians, a comma left in a number (atof('3,87') returns 3), or fields shifted because an empty phone number was swallowed by the split.
Can I skip the square root?
Yes. Comparing x^2 + y^2 gives the same order as comparing the real distances, because sqrt and multiplying by the Earth radius are increasing functions.