### Exercice 1

def pos_min_local(M):
    '''Détermine une position d'un minimum local d'une matrice (liste de listes toutes de même taille ou tableau numpy de dimension 2).
Si la matrice ne contient que des entiers naturels, la complexité est linéaire en le maximum de la matrice.
Sinon, elle est quadratique et on peut tout aussi bien chercher le minimum global par un algorithme naïf.
Un algorithme diviser-pour-régner en temps linéaire existe, mais il est laborieux à implémenter
et la stratégie de l'algorithme ci-dessous fait que la complexité est rarement pire que linéaire.'''
    assert len(M) > 0, "Matrice vide"
    assert len(M[0]) > 0, "Matrice vide"
    lignes, colonnes = len(M), len(M[0])
    l = 0
    c = 0
    while M[l][c] > 0:
        l_min = l
        c_min = c
        mini = M[l][c]
        if (l > 0 and M[l-1][c] < mini): # pas fier de ces if, mais bon…
            l_min, c_min, mini = l-1, c, M[l-1][c]
        if (l < lignes-1 and M[l+1][c] < mini):
            l_min, c_min, mini = l+1, c, M[l+1][c]
        if (c > 0 and M[l][c-1] < mini):
            l_min, c_min, mini = l, c-1, M[l][c-1]
        if (c < colonnes-1 and M[l][c+1] < mini):
            l_min, c_min, mini = l, c+1, M[l][c+1]
        if l_min == l and c_min == c:
            return (l, c)
        l, c = l_min, c_min
    return l, c

### Exercice 2

def memes_elements(L, LL):
    '''Détermine si les deux listes en argument ont le même ensemble d'éléments.'''
    for x in L:
        if x not in LL:
            return False
    for x in LL: # Ne pas oublier !
        if x not in L:
            return False
    return True

### Exercice 2 bis

def permutation(L, LL):
    '''Détermine si L et LL ont les mêmes éléments comptés avec leur multiplicité.
La complexité est acceptable (n log n), et le programme est le plus simple à écrire possible.'''
    L1 = list(L) # copie
    L2 = list(LL)
    L1.sort() # ne marche donc pas pour des listes quelconques
    L2.sort()
    return L1 == L2

def permutation2(L,LL): # hors-programme
    '''Idem permutation, avec une complexité pire (quadratique) mais un algorithme intuitif.
De plus, les éléments peuvent être quelconques.'''
    L2 = list(LL)
    try:
        for x in L:
            L2.remove(x)
        return len(L2) == 0
    except:
        return False

def permutation3(L, LL):
    '''Vive les dictionnaires ! Ici, il faut que les éléments de L soient hachables.
Complexité linéaire en pratique (et en trichant).'''
    eltsL, eltsLL = {}, {}
    n = len(L)
    if len(LL) != n:
        return False
    for i in range(n):
        try:
            eltsL[L[i]] += 1
        except:
            eltsL[L[i]] = 1
        try:
            eltsLL[LL[i]] += 1
        except:
            eltsLL[LL[i]] = 1
    for cle in eltsL:
        if eltsLL[cle] != eltsL[cle]:
            return False
    return True

### Exercice 3

def plus_longue_sous_liste_identique(L):
    '''Renvoie la position de départ et la longueur de la plus longue sous-liste d'éléments identiques dans L.
En cas d'égalité, la première est considérée.'''
    lmax = 0
    imax = 0
    i = 0
    l = 1
    while i < len(L)-1:
        if L[i] == L[i+1]:
            l += 1
        else:
            if l > lmax:
                lmax, imax = l, i-l+1
            l = 1
        i += 1
    if l > lmax:
        lmax, imax = l, i-l+1
    return (imax, lmax)

### Exercice 4

def plus_petit_rapport(L):
    '''Renvoie l'indice du couple d'entiers strictement positifs dans la liste L
dont le rapport entre le deuxième et le premier élément est minimal.
En cas d'égalité, le premier indice est considéré.'''
    imin = 0
    for i in range(1, len(L)):
        if L[i][0] * L[imin][1] < L[i][1] * L[imin][0]: # pratique pour éviter les flottants
            imin = i
    return imin

### Exercice 4 bis

def repetition(L):
    '''Détermine combien de fois deux indices consécutifs de la liste L
contiennent une structure partageant leur premier élément.
S'il y a trois indices consécutifs, le compteur est augmenté de deux par exemple.'''
    c = 0
    for i in range(len(L)-1):
        if L[i][0] == L[i+1][0]:
            c += 1
    return c

def existe_repetition(L):
    '''Détermine si deux indices consécutifs de la liste L
contiennent une structure partageant leur premier élément.'''
    c = 0
    for i in range(len(L)-1):
        if L[i][0] == L[i+1][0]:
            return True
    return False

### Exercice 5

def plus_frequent(L):
    '''Retourne le nombre le plus fréquent dans une liste d'entiers naturels.
En cas d'égalité, le plus petit nombre est retourné.
La complexité est linéaire en le produit du maximum de la liste et de sa taille.'''
    assert len(L) > 0, "Liste vide"
    k = max(L)
    occurrences = [0]*(k+1) # Attention !
    for n in L:
        occurrences[n] += 1
    max_occ = occurrences[0]
    plus_frequent = 0
    for i in range(1, k+1):
        if occurrences[i] > max_occ:
            max_occ, plus_frequent = occurrences[i], i
    return plus_frequent

# On pourrait écrire une variante dans laquelle le maximum est en paramètre.
    
def plus_frequents(L):
    '''Variante renvoyant une liste regroupant les valeurs les plus fréquentes à égalité, dans l'ordre croissant.'''
    assert len(L) > 0, "Liste vide"
    k = max(L)
    occurrences = [0]*(k+1) # Attention !
    for n in L:
        occurrences[n] += 1
    max_occ = occurrences[0]
    plus_frequents = [0]
    for i in range(1, k+1):
        if occurrences[i] > max_occ:
            max_occ, plus_frequents = occurrences[i], [i]
        elif occurrences[i] == max_occ:
            plus_frequents.append(i)
    return plus_frequents

### Exercice 5 bis

def caractere_plus_frequent(s):
    '''Retourne le nombre le plus fréquent dans une chaîne de caractères ASCII 7 bits.
En cas d'égalité, le caractère de plus code ASCII est retourné.
La complexité est linéaire en la taille de la chaîne de caractères (avec une autre table de caractères, il faut multiplier par la taille de cette table).'''
    assert len(L) > 0, "Chaîne vide"
    occurrences = [0]*(128)
    for n in L:
        occurrences[ord(n)] += 1
    max_occ = occurrences[0]
    plus_frequent = 0
    for i in range(1, 128):
        if occurrences[i] > max_occ:
            max_occ, plus_frequent = occurrences[i], i
    return chr(plus_frequent)

# Une version possible de complexité « quasi-linéaire » pour une liste d'objets ordonnables : trier et appeler plus_longue_sous_liste_identique

### Exercice 6

def recherche_motif(mat, motif):
    '''Détermine la position du coin en haut à gauche (minimisant les deux indices) d'un motif dans une matrice contenant des éléments quelconques.
Si le motif apparaît plusieurs fois, la position retournée est celle à la première ligne possible, et à même ligne à la première colonne possible.'''
    assert len(mat) > 0, "Matrice vide"
    assert len(mat[0]) > 0, "Matrice vide"
    assert len(motif) > 0, "Motif vide"
    assert len(motif[0]) > 0, "Motif vide"
    l, c = len(mat), len(mat[0])
    lm, cm = len(motif), len(motif[0])
    for i in range(l-lm+1):
        for j in range(c-cm+1):
            im, jm = 0, 0
            while im < lm and (motif[im][jm] == None or motif[im][jm] == mat[i+im][j+jm]):
                jm += 1
                if jm == cm:
                    im, jm = im+1, 0
            if im == lm:
                return (i, j) # Retour de la première occurrence, on peut aussi stocker le tout dans une liste
    raise ValueError("Introuvable")

### Exercice 7

def zeros_ensemble(mat):
    '''Détermine si tous les 0 d'une matrice sont ensemble, c'est-à-dire sur une même composante connexe.'''
    m = len(mat)
    if m == 0:
        return True
    n = len(mat[0])
    if n == 0:
        return True
    i,j = 0,0
    trouve = False
    while not trouve and i < m and j < n:
        if mat[i][j] == 0:
            trouve = True
    if not trouve:
        return True
    pile = [(i, j)]
    while len(pile) > 0:
        (l, c) = pile.pop()
        mat[l][c] = None
        if l > 0 and mat[l-1][c] == 0:
            pile.append((l-1, c))
        if c > 0 and mat[l][c-1] == 0:
            pile.append((l, c-1))
        if l < m and mat[l+1][c] == 0:
            pile.append((l+1, c))
        if c < n and mat[l][c+1] == 0:
            pile.append((l, c+1))
    i, j = 0, 0
    while i < m and j < n:
        if mat[i][j] == 0:
            return False
    return True

### Exercice 7 bis

def deux_voisins(L):
    '''Détermine si L contient deux éléments L[i1][j1] et L[i2][j2], qui sont des couples d'entiers,
distancés d'un en norme 1. On admet que les entiers sont tous positifs.
On admet aussi qu'aucun élément n'apparait deux fois dans deux listes de L.'''
    if len(L) < 2:
        return False
    maxi, maxj = L[0][0][0], L[0][0][1]
    for liste in L:
        for element in liste:
            maxi = max(maxi, element[0])
            maxj = max(maxj, element[1])
    M = [[0 for j in range(maxj+1)] for i in range(maxi+1)]
    voisins = [(i, j) for i in range(-1, 2) for j in range(-1, 2) if i, j != 0, 0]
    for indice, liste in enumerate(L):
        for x, y in liste:
            M[x][y] = indice+1
            for (dx, dy) in voisins: # tant pis pour l'optimisation
                if 0 <= x+dx <= maxi and 0 <= y+dy <= maxj and M[x+dx][y+dy] not in [0, indice+1]:
                    return True
    return False

### Exercice 7 ter

def true_ensemble(l):
    '''Détermine si tous les True sont ensemble dans la liste de booléens L.
On notera que cela caractérise exactement les listes bitoniques de booléens avec la relation d'ordre intuitive sur cet ensemble.'''
    n = len(l)
    k = 0
    while (k < n and not(l[k])):
        k += 1
    while (k < n and l[k]):
        k += 1
    while (k < n and not(l[k])):
        k += 1
    return k == n

def true_ensemble_bis(l):
    '''Autre astuce pour la même spécification que la fonction précédente.'''
    phase = 0
    for b in l:
        phase += (phase % 2 != b)
    return phase < 3

### Exercice 8

def plus_petit_ecart(L):
    '''Détermine la position i de la liste croissante L
telle que L[i+1]-L[i] minimise l'écart entre deux valeurs consécutives.'''
    i = 0
    for k in range(1, len(L)-1):
        if L[k+1]-L[k] < L[i+1]-L[i]:
            i = k
    return i

### Exercice 9

def possibles(M, i, j):
    '''Détermine la liste des nombres de 1 à n
qui ne sont ni dans la ligne i ni dans la colonne j de M (matrice carrée).
Fonction de base pour un sudoku, par exemple.'''
    n = len(M)
    libres = [True for i in range(n)]
    for k in range(n):
        libres[M[i][k]-1] = False
        libres[M[k][j]-1] = False
    return [i+1 for i in range(n) if libres[i]]

### Exercice 10

def moyenne(l):
    return sum(l)/len(l)

def moyennise(l):
    '''Retourne la liste des moyennes de chaque élément de la liste en entrée et de son ou ses voisins.'''
    res = []
    for i in range(len(l)):
        res.append(moyenne(l[max(0, i-1):i+2]))
    return res

# Les moyennes sont calculées à l'aide d'extractions pour ne pas faire de tests aux bords de la liste.

def moyennisebis(M):
    '''Généralisation à une matrice.'''
    res = []
    for i in range(len(M)):
        resbis = []
        for j in range(len(M[i])):
            resbis.append(moyenne([M[k][l] for k in range(max(0, i-1), min(i+2, len(M))) for l in range(max(0, j-1), min(j+2, len(M[0])))]))
        res.append(resbis)
    return res

### Exercice 11

from math import sqrt

def distance(A, B, norme=2):
    '''Retourne la distance entre les points A et B en dimension quelconque.
Si le troisième argument est omis ou vaut 2, on renvoie la norme euclidienne.
S'il vaut 1, on renvoie la somme des distances selon les axes.
Sinon, on renvoie le maximum des distances selon les axes.'''
    assert len(A) == len(B), "Les dimensions ne correspondent pas."
    somme = 0
    for i in range(len(A)):
        if norme == 2:
            somme += (A[i]-B[i])**2
        elif norme == 1:
            somme += abs((A[i]-B[i]))
        else:
            somme = max(somme, abs((A[i]-B[i])))
    if norme == 2:
        return sqrt(somme)
    else:
        return somme

def plus_proche(pos, liste, norme=2):
    '''Retourne l'indice dans une liste du point le plus proche d'un point donné.
La norme (2, 1 ou infinie) est un paramètre optionnel.
La dimension est en pratique quelconque.'''
    n = len(liste)
    assert n > 0, "Liste vide."
    min_dist = distance(pos, liste[0], norme)
    min_ind = 0
    for i in range(1, n):
        d = distance(pos, liste[i], norme)
        if d < min_dist:
            min_dist = d
            min_ind = i
    return min_ind

### Exercice 12

def geometrique(l):
    '''Détermine si l contient les premiers éléments d'une suite géométrique.'''
    n = len(l)
    if n <= 1:
        return True
    if n == 2:
        return l[0] != 0 or l[1] == 0
    i = 1
    while i < n-1 and l[i+1]*l[i-1] == l[i]**2: # Astuce pour éviter les divisions par 0
        i += 1
    return i == n-1

### Exercice 12 bis

def arithmetique_ou_geometrique(l):
    '''Détermine si l contient les premiers éléments d'une suite arithmétique ou géométrique.'''
    n = len(l)
    if n == 0:
        return "Liste vide"
    i = 1
    while i < n and l[i] == l[i-1]:
        i += 1
    if i == n:
        return "Constante"
    elif i > 1:
        return "Ni arithmétique ni géométrique"
    if n <= 2:
        return "Arithmétique et géométrique mais non constante (donc 2 éléments)."
    while i < n-1 and l[i]-l[i-1] == l[i+1]-l[i]:
        i += 1
    if i == n-1:
        return "Arithmétique"
    elif i > 1:
        return "Ni arithmétique ni géométrique"
    while i < n-1 and l[i+1]*l[i-1] == l[i]**2:
        i += 1
    if i == n-1:
        return "Géométrique"
    return "Ni arithmétique ni géométrique"

### Exercice 13

def croissante_ou_decroissante(L):
    '''Détermine si la liste L est croissante ou décroissante ou constante.'''
    i = 0
    while i < len(L)-1 and L[i] == L[i+1]:
        i += 1
    if i == len(L)-1:
        return "Constante"
    if L[i] < L[i+1]:
        while i < len(L)-1 and L[i] <= L[i+1]:
            i += 1
        if i == len(L)-1:
            return "Croissante"
        else:
            return "Rien"
    else:
        while i < len(L)-1 and L[i] >= L[i+1]:
            i += 1
        if i == len(L)-1:
            return "Decroissante"
        else:
            return "Rien"

### Exercice 13 bis

def bitonique(L):
    '''Détermine si la liste L est bitonique, c'est-à-dire croissante puis décroissante.'''
    i = 0
    while i < len(L)-1 and L[i] <= L[i+1]:
        i += 1
    while i < len(L)-1 and L[i] >= L[i+1]:
        i += 1
    return i == len(L)-1


### Exercice 14

def tourne_matrice(M):
    '''Retourne la matrice M tournée d'un quart de tour dans le sens horaire.'''
    N = []
    lignes, colonnes = len(M), len(M[0])
    for i in range(colonnes):
        N.append([M[j][i] for j in range(lignes-1, -1, -1)])
    return N

### Exercice 14 bis

def cree_damier(M):
    '''Crée à partir de la matrice M de forme (n, 2n) une matrice de forme (2n, 2n)
en ajoutant des zéros pour former un damier. En ligne 0, colonne 0, il y a un vrai élément.'''
    N = []
    n = len(M)
    for i in range(n):
        ligne = []
        for j in range(n//2):
            if i % 2 == 1:
                ligne.append(0)
            ligne.append(M[i][j])
            if i % 2 == 0:
                ligne.append(0)
        N.append(ligne)
    return N

def annule_damier(M):
    '''Crée à partir de la matrice M de forme (2n, 2n) une matrice de forme (2n, n)
en retirant des zéros qui formaient un damier. En ligne 0, colonne 0, il y avait un vrai élément.'''
    N = []
    n = len(M)
    for i in range(n):
        ligne = []
        for j in range(i % 2, n, 2):
            ligne.append(M[i][j])
        N.append(ligne)
    return N

### Exercice 15

from random import randint

def promenade(L, l, n):
    '''Simule une promenade aléatoire sur une grille de taille 2L par 2l.
La promenade s'arrête après n pas ou une sortie de la grille.
La fonction retourne un message annonçant comment la promenade s'est terminée.'''
    x = 0
    y = 0
    k = 0
    while (abs(x) <= L and abs(y) <= l and k < n):
        k += 1
        r = randint(0, 3)
        if r == 0:
            x = x + 1
        elif r == 1:
            y = y + 1
        elif r == 2:
            x = x - 1
        else:
            y = y - 1
    if x > L:
        return "Sortie à droite"
    if x < -L:
        return "Sortie à gauche"
    if y > l:
        return "Sortie en haut"
    if y < l:
        return "Sortie en bas"
    return "Pas de sortie"

### Exercice 15 bis

from random import choice

def promenade(graphe, depart, n):
    '''Simule une promenade aléatoire sur un graphe (a priori orienté) donné en tant que liste de listes d'adjacence.
Les sommets du graphe sont alors nommés par leur indice de 0 à n-1, où n est le nombre de sommets
On suppose qu'il n'y a pas de blocage (donc tous les sommets ont au moins un successeur).
La promenade s'arrête après n pas.
La fonction retourne le sommet où la promenade s'est terminée.'''
    sommets = len(graphe)
    position = depart
    if position < 0 or position >= sommets:
        raise ValueError("Sommet de départ invalide")
    for i in range(n):
        position = choice(graphe[position])
        if position < 0 or position >= sommets:
            raise ValueError("Position intermédiaire invalide")
    return position

### Exercice 16

def intersection(pointA,pointB,pointC,pointD):
    '''Détermine si les segments [AB] et [CD] se chevauchent.'''
    if pointA[0] == pointB[0]: # [AB] est vertical
        if pointC[0] == pointD[0]: # [CD] aussi
            return pointA[0] == pointC[0] and max(pointA[1],pointB[1]) >= min(pointC[1],pointD[1]) and min(pointA[1],pointB[1]) <= max(pointC[1],pointD[1])
            # Les lignes verticales doivent être à la même abscisse et le point le plus haut de chaque segment doit être plus haut que le point le plus bas de l'autre
        elif pointC[1] == pointD[1]: # [CD] est horizontal, on doit parler de l'abscisse d'intersection par rapport à ce segment
            return min(pointA[1],pointB[1]) <= pointC[1] <= max(pointA[1],pointB[1]) and min(pointC[0],pointD[0]) <= pointA[0] <= max(pointC[0],pointD[0])
        else:
            ordonnee_intersection_droites = pointC[1] + (pointD[1]-pointC[1])/(pointD[0]-pointC[0])*(pointA[0]-pointC[0])
            return min(pointA[1],pointB[1]) <= ordonnee_intersection_droites <= max(pointA[1],pointB[1]) and min(pointC[1],pointD[1]) <= ordonnee_intersection_droites <= max(pointC[1],pointD[1])
            # L'intersection des droites doit être entre les extrema des segments dans les trois cas, et les tests sont légèrement différents
    elif pointC[0] == pointD[0]:
        (pointA,pointB,pointC,pointD) = (pointC,pointD,pointA,pointB) # pour ne pas risquer de se tromper dans le copier-coller
        if pointC[1] == pointD[1]:
            return min(pointA[1],pointB[1]) <= pointC[1] <= max(pointA[1],pointB[1]) and min(pointC[0],pointD[0]) <= pointA[0] <= max(pointC[0],pointD[0])
        ordonnee_intersection_droites = pointC[1] + (pointD[1]-pointC[1])/(pointD[0]-pointC[0])*(pointA[0]-pointC[0])
        return min(pointA[1],pointB[1]) <= ordonnee_intersection_droites <= max(pointA[1],pointB[1]) and min(pointC[1],pointD[1]) <= ordonnee_intersection_droites <= max(pointC[1],pointD[1])
        # Idem
    else:
        penteAB = (pointB[1]-pointA[1])/(pointB[0]-pointA[0])
        penteCD = (pointD[1]-pointC[1])/(pointD[0]-pointC[0])
        if penteAB != penteCD:
            abscisse_intersection_droites = (pointC[1] - penteCD * pointC[0] - pointA[1] + penteAB * pointA[0]) / (penteAB-penteCD)
            # On résout l'équation dans le cas général, ce qui donnt l'abscisse du point d'intersection des droites
            return min(pointA[0],pointB[0]) <= abscisse_intersection_droites <= max(pointA[0],pointB[0]) and min(pointC[0],pointD[0]) <= abscisse_intersection_droites <= max(pointC[0],pointD[0])
            # L'abscisse doit être entre les abscisses extrémales des segments (donc l'ordonnée le serait aussi)
        else: # Cas de droites parallèles non verticales
            ordonnee_en_zero_AB = pointA[1] - penteAB*pointA[0]
            ordonnee_en_zero_CD = pointC[1] - penteCD*pointC[0]
            if ordonnee_en_zero_AB != ordonnee_en_zero_CD: # droites non confondues
                return False
            return max(pointA[1],pointB[1]) >= min(pointC[1],pointD[1]) and min(pointA[1],pointB[1]) <= max(pointC[1],pointD[1])
            # Comme dans le cas de lignes verticales sur la même abscisse, les ordonnées extrémales doivent se chevaucher

### Exercice 17

def hitbox_dr(disque, rectangles):
    '''Détermine si le disque donné en tant que couple (coordonnées du centre, rayon)
touche ou entoure au moins un des rectangles pleins dans une liste,
chaque rectangle étant donné comme le couple (coordonnées du coin inférieur gauche,coordonnées du coin supérieur droit).'''
    (centre, rayon) = disque
    (x, y) = centre
    for rectangle in rectangles:
        (coin_bg, coin_hd) = rectangle
        (x1, y1) = coin_bg
        (x2, y2) = coin_hd
        if x1 <= x <= x2 and y1 - rayon <= y <= y2 + rayon: # Le centre est aligné verticalement avec un point du rectangle et trop proche
            return True
        if x1 - rayon <= x <= x2 + rayon and y1 <= y <= y2: # Idem mais horizontalement
            return True
        if (x1 - x)**2 + (y1 - y)**2 < rayon**2: # Le centre est trop près du coin en bas à gauche
            return True
        if (x1 - x)**2 + (y2 - y)**2 < rayon**2: # Idem mais en haut à gauche
            return True
        if (x2 - x)**2 + (y1 - y)**2 < rayon**2: # Idem mais en bas à droite
            return True
        if (x2 - x)**2 + (y2 - y)**2 < rayon**2: # Idem mais en haut à droite
            return True
    return False

def distmax(point, points):
    '''Calcule la plus grande distance euclidienne entre le point donné
et un des (quatre en pratique) points de la séquence en deuxième argument. On utilise la fonction distance de l'exercice 12.'''
    return max([distance(point, point2) for point2 in points])

def hitbox_cr(cercle, rectangles):
    '''Détermine si le cercle donné en tant que couple (coordonnées du centre, rayon)
intersecte au moins un des rectangles pleins dans une liste,
chaque rectangle étant donné comme le couple (coordonnées du coin inférieur gauche,coordonnées du coin supérieur droit).'''
    (centre, rayon) = cercle
    (x, y) = centre
    for rectangle in rectangles:
        (coin_bg, coin_hd) = rectangle
        (x1, y1) = coin_bg
        (x2, y2) = coin_hd
        coin_bd = (x1, y2)
        coin_hg = (x2, y1)
        coins = (coin_bg, coin_bd, coin_hg, coin_hd)
        troploin = False
        if distmax(centre, coins) < rayon: # Le cercle entoure totalement les quatre coins, donc le rectangle. Seul le disque intersecte (différence avec hitbox).
            troploin = True # Pour ne pas utiliser de break
        if x1 <= x <= x2 and y1 - rayon <= y <= y2 + rayon and not troploin: # Le centre est aligné verticalement avec un point du rectangle et trop proche
            return True
        if x1 - rayon <= x <= x2 + rayon and y1 <= y <= y2 and not troploin: # Idem mais horizontalement
            return True
        if (x1 - x)**2 + (y1 - y)**2 < rayon**2 and not troploin: # Le centre est trop près du coin en bas à gauche
            return True
        if (x1 - x)**2 + (y2 - y)**2 < rayon**2 and not troploin: # Idem mais en haut à gauche
            return True
        if (x2 - x)**2 + (y1 - y)**2 < rayon**2 and not troploin: # Idem mais en bas à droite
            return True
        if (x2 - x)**2 + (y2 - y)**2 < rayon**2 and not troploin: # Idem mais en haut à droite
            return True
    return False

def hitbox_dd(disque, disques):
    '''Détermine si le disque en tant que couple (coordonnées du centre, rayon)
intersecte au moins un des disques de la liste, donnés sous la même convention.'''
    c, r = disque
    x, y = c
    for centre, rayon in disques:
        xx, yy = centre
        if (xx - x)**2 + (yy - y)**2 <= (rayon + r)**2:
            return True
    return False