Bonjour,

J'ai trouvé un énoncé d'une épreuve de CAPES dont voici le lien : http://www.mediafire.com/view/88tnisaotvsl15o/EPREUVE_OPTIONNELLE_INFORMATIQUE_(1).pdf

Le problème que j'ai pas pu résoudre est "C)IMAGE".

Je souhaite que quelqu'un me donne une piste d'un algorithme optimal.

J'ai trouvé un problème semblable de PROLOGIN 2011 : 

http://www.prologin.org/training/challenge/demi2011/rectangles

J'ai trouvé un code en python sur ce forum pour le problème de prologin. J'ai essayé de l'adapté à mon problème mais en vain :

def aire(n, b):
    xs = sorted(set(b[::2]))
    z = dict(zip(xs,range(len(xs))))
    r = [[]for foo in range(len(z)-1)]
    b = zip(b[::4],b[1::4],b[2::4],b[3::4])
  
      
    for x0,y0,x1,y1 in b:
      for i in range(z[x0],z[x1]):
	r[i].append([y0,y1])
	
    del z
    del b
    e = R = 0
    for i in r:
        E = [[0,0]]
        for y0,y1 in sorted(i):
	  if y0<E[-1][1]:
	    if y1>E[-1][1]:
	      E[-1][1]=y1
	      
	  else:
	    E.append([y0,y1])
        R += sum([m-p for p,m in E])*(xs[e+1]-xs[e])
        e += 1
    return R
    
  
if __name__ == '__main__':
    n = int(raw_input())
    b = [int(_) for _ in raw_input().split()]
 
    print aire(n,b)

Merci à l'avance

-
Edité par victor2 20 avril 2014 à 20:43:28

Bonjour,

Oui j'ai vu çà.

Up

Ce problème m'intrigue, je vois aucun algorithme. J'aimerais bien savoir comment résoudre ce problème.

"

http://www.mediafire.com/view/88tnisaotvsl15o/EPREUVE_OPTIONNELLE_INFORMATIQUE_(1).pdf

Le problème que j'ai pas pu résoudre est "C)IMAGE".

"

Personnellement, j'irais progressivement.

Je prends les rectangles les uns après les autres.

Si le suivant n'a pas d'intersection avec la forme précédentes, j'ai deux options.

- 1 - soit il est inclus et je ne compte pas la nouvelles figures

- 2 - soit il est exclu et j'ajoute le périmètre complet de la nouvelle figure.

Si nous avons des intersections :

Le périmèter sera le total des deux périmèter moins deux fois la longueur des segments formant l'intersection.

Avant d'avoir fini, il faudra ajouter l'éventuel périmèter intérieur. (le prérimètre du/des rectangle(s) vide(s) au milieu). Périmètre que l'on trouve grace aux différentes intersections des figures de départ.

Evidement, je n'ai fait aucun algorithme mais un simple pseudo code. J'espère que cela va te diriger.

Une autre possibilité :

1) on regarde d'abord un problème plus simple :  on a une matrice de booléens qui indique si les cases d'une grille sont occupées ou non => calculer la longueur de la frontière

La solution (brute) est très simple : on compte le nombre de fois où le contenu d'une case est différent de sa voisine de droite, ça donne le nombre de segments verticaux à compter dans le périmètre.  Idem pour les horizontaux, en regardant la case de dessous.

2) si ce sont des rectangles dans une grille discrête, on peut faire un peu mieux : pour chaque ligne on fait l'union des intervalles occupés par les rectangles qui intersectent la ligne. Le nombre de segments verticaux, c'est 2 fois le nombre d'intervalles. (idem pour colonnes et horizontaux).

3) on ramène le problème initial au problème "discret" ci-dessus, en constituant la liste ordonnée des abscisses et ordonnées "réelles", et en traduisant les rectangles "réels" en rectangles discrets.

-
Edité par michelbillaud 27 avril 2014 à 9:18:11