Corrigé CCINP 2026 Sciences industrielles MP — Partie V (Q37 à Q46) : Optimisation du parcours de marquage (ITC) : dictionnaire, plus proche extrémité, glouton

Exigence 1.2.3 : minimiser les distances parcourues lors d'un tracé. Les lignes à tracer sont extraites d'un fichier texte dont la première ligne est un en-tête et dont chaque ligne suivante donne les coordonnées (en m) des deux extrémités d'un trait, séparées par des tabulations. On les range dans un dictionnaire traces : clé entière = numéro du trait dans l'ordre de lecture du fichier (à partir de $0$) ; valeur = liste de deux 2-uplets de flottants $(x_i,y_i)$. Exemple : carré de $1\mathrm{m}$ divisé en quatre (fichier carre.txt, Figure 17), dont le dictionnaire commence par \{0: [(0.0, 0.0), (1.0, 0.0)], 1: [(0.0, 0.0), (0.0, 1.0)], ...\}.

xp1	yp1	xp2	yp2
0.	0.	1.	0.
0.	0.	0.	1.
1.	1.	0.	1.
1.	1.	1.	0.
0.5	0.	0.5	1.
0.	0.5	1.	0.5

    

{ Figure 17 — Fichier carre.txt (à gauche) et tracé obtenu (à droite).}

Script du DR (Q38), création du dictionnaire (les ... sont à compléter) :

nom_fichier = "rugby.txt"
traces = {}
fichier = open(nom_fichier, "r"):
    k = 0
    for line in fichier:
        if k == 0:
            k += 1
        else:
            ligne = line.split()
            ...
            ...
            traces[...] = [P1, P2]
            k += 1
fichier.close()

Fonction PPE (plus proche extrémité) donnée au DR (Q41), et squelette de trajet (Q42) :

def PPE(init, voisin):
    dmin = float("inf")
    for k in voisin:
        for j in range(2):
            dist_voisin = distance(init, voisin[k][j])
            if dist_voisin < dmin:
                dmin = dist_voisin
                (t, p) = (k, j)
    return (t, p)

def trajet(init, traits):
    parcours = []
    pos_init = init
    for k in range(len(traits)):
        ...
        ...
        ...
        del traits[...]
    return parcours

Une ligne se trace d'un seul tenant, dans un sens quelconque ; on minimise, après chaque trait, la distance euclidienne jusqu'au début du trait suivant. trajet(init, traits) renvoie la liste des couples (clé du trait, indice de l'extrémité de départ). Pour Q45, le DR compare le test dist_voisin < dmin (cas a) et dist_voisin <= dmin (cas b).

Q37. Rôle de la variable k et de la structure conditionnelle sur sa valeur.
Q38. Les deux lignes manquantes et la clé du dictionnaire.
Q39. Écrire distance(A, B) (distance euclidienne) avec sqrt du module math.
Q40. Signature et spécification de PPE.
Q41. Commenter chaque ligne de PPE.
Q42. Compléter trajet.
Q43. Après trajet((0,0), traces), peut-on encore utiliser traces ?
Q44. traces1 = copy(traces) placé juste après fichier.close() résout-il le problème ?
Q45. Conséquence des cas a et b sur le choix de l'extrémité la plus proche.
Q46. Dessiner, pour trajet((0,0), traces) sur carre.txt et dans les deux cas, l'ordre de tracé (numéro), le sens (flèche) et les trajets sans peinture (pointillés numérotés et fléchés).