Coding Solution

Defibrillators – CodinGame solution in C

Easystring parsingdistance formulalinear searchUpdated
Short answer

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

  1. Read the user positionRead the longitude and latitude as strings, replace the ',' with '.', parse them as floating-point numbers and convert them to radians.
  2. 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.
  3. 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.
  4. 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.
  5. Keep the minimumTrack the smallest distance seen and the name attached to it in a single pass, then print that name.

Complexity

TimeO(N)
SpaceO(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;
}

Common mistakes

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.

Similar puzzles

★ 5.0 · 16 reviews · 928 users Add to Chrome