J'étudie depuis quelques temps sur le site France IOI, que je vous recommande fortement si vous commencez à coder, et malheuresement je bloque sur un probleme mettant en jeu les connaissances sur les conditions boléenes et l'analyse graphique de rectangles.

Voici le sujet:

http://www.france-ioi.org/algo/task.php?idChapter=648&iOrder=7

J'ai reussi a créer un programmes répondant à 2 tests sur 8 mais je pense fortement que j'ai oublie une conditions ce qui bloque totelemnt la suite des tests. 

 Aussi, voila les resultats donnés par l'algorithme de france IOI

Très fun comme exercice !

Alors pour la théorie, voici comment on procède. Soit 2 rectangles R1 et R2. On accède à l'abscisse minimum avec la notation T1.left et la maximum avec R1.right. Pour l'ordonnée minimum on aura R1.bottom et pour l'ordonnée max on aura R1.top.

Voici la clé du succès. Il suffit de se rendre compte que si R1.left > R2.right, alors peu import l'ordonnée de l'un ou de l'autre, il ne pourront jamais avoir d'intersection. Je peux recommencer le raisonnement pour R1.right < R2.left et à nouveau, il n'y aura jamais d'intersection. Tu auras compris que ça s'applique aussi à R1.top < R2.bottom et R1.bottom > R2.top.

Si n'importe laquelle de ces 4 précédente condition n'est pas satisfaite, alors il y a forcément collision.

EDIT: désolé mais mes signes plus petits et plus grands sont une fois de plus horriblement mutilés par le forum. Tu auras compris que < c'est plus petit que et > c'est plus grand que.

-
Edité par Dan737 3 septembre 2019 à 15:25:16

Salut ! 

Le mieux pour cet exercice serait de suivre cette méthode : 

Je ne peux que te montrer le cheminement proposé par france ioi pour sa correction mais pas la correction en elle-même ! Bonne chance :) 

Bonjour je ne comprend toujours pas 

voici mon code:

nbpaires = int(input())

for i in range(nbpaires):

   absmin1 = int(input())

   absmax1 = int(input())

   ordmin1 = int(input())

   ordmax1 = int(input())

   absmin2 = int(input())

   absmax2 = int(input())

   ordmin2 = int(input())

   ordmax2 = int(input())     

   carré1 = (absmax1 - absmin2) * (ordmax1 - ordmin1)

   carré2 = (absmax2 - absmin2) * (ordmax2 - ordmin2)

   if carré1 > carré2 and absmin1 > absmin2 and ordmin1 > ordmin2:

      print("NON")

   else:

      print("OUI")

Pourquoi absmin2 dans le calcul de carré1 ?

-
Edité par entwanne 3 avril 2019 à 7:47:15

Tu ne l'auras pas.

À quoi le grec ?

Salut je peut avoir le code complet de la caserne de pomopier svp les mecs c'est urgent ma scolarité en depant 

Tant pis alors, je n'aurai pas ma réponse. J'imagine que c'était à la fraise.

Bonjour, je repost ici car je n'arrive pas a trouvé une solution viable même après avoir suivi vos conseils. Voici mon donc mon code : 

paireZone=int(input())

for loop in range(paireZone):

   R1left = int(input())

   R1right = int(input())

   R1bottom = int(input())

   R1top = int(input())

   R2left = int(input())

   R2right = int(input())

   R2bottom = int(input())

   R2top = int(input())     

   if  (R1left > R2right) or (R1right < R2left) or (R1top < R2bottom) or (R2bottom > R1top):

      print("NON")

   else:

      print("OUI")

Salut,

Si quelqu'un a un petit conseil, je crois que je me complique la vie avec ma façon de faire. Ce ne serait pas moins compliqué si je faisais l'inverse ? C'est à dire définir les moments ou ça ne se croise pas plutôt que ce ou ça se croise ? Le code n'est pas fini, je pense qu'il peut fonctionner en continuant sur cette voie si je continue de réfléchir, mais je ne suis pas contre exemple plus simple.

Merci !

nbPaires = int(input())
for loop in range(nbPaires):
   xMin1 = int(input())
   xMax1 = int(input())
   yMin1 = int(input())
   yMax1 = int(input())
   xMin2 = int(input())
   xMax2 = int(input())
   yMin2 = int(input())
   yMax2 = int(input())
if ((xMax1 > xMin2) and (yMax1 > yMin2)):
    if ((xMin1 < xMin2) and (yMin1 < yMin2)):
        print("OUI")
if ((xMax2 > xMin1) and (yMax2 > yMin1)):
    if ((xMin2 < xMin1) and (yMin2 < yMin1)):
        print("OUI")
if ((xMax1 > xMin2) and (yMin1 < yMax2)):
    if ((xMin1 < xMin2) and (yMax1 > yMax2)):
        print("OUI")
if ((xMax2 > xMin1) and (yMin2 < yMax1)):
    if ((xMin2 < xMin1) and (yMax2 > yMax1)):
        print("OUI")
else:
    print("NON")

Salut,

Tu rencontreras en effet des soucis avec ton code actuel puisque le else n'est valable que pour la condition ligne 20, et s'affichera dans tous les cas si cette condition est fausse (même si la condition ligne 17 ou celle ligne 21 sont vraies par exemple).

Et sinon, pour limiter les conditions, dans un premier temps je te propose de classer tes rectangles de façon à ce que les coordonnées 1 correspondent toujours à celui le plus à gauche par exemple.

entwanne a écrit:

Et sinon, pour limiter les conditions, dans un premier temps je te propose de classer tes rectangles de façon à ce que les coordonnées 1 correspondent toujours à celui le plus à gauche par exemple.

Mais si pendant la saisie je décide que mon 1 est a droite et que mon 2 est a gauche (ce qui pourrait arriver) Je ne peux pas utiliser cette méthode, si ?

Merci pour le retour rapide !

edit: Tu me conseils de rajouter une condition au debut qui permet de trier ca automatiquement si je comprend bien ?

-
Edité par Heisenberg-2.0 11 août 2019 à 19:05:18

Oui, il s'agit justement d'inverser les deux rectangles après la saisie, pour simplifier toutes les conditions suivantes.

Une autre solution, à base des fonctions min et max serait de calculer les coordonnées rectangle d'intersection et d'en déduire s'il existe ou pas.

-
Edité par entwanne 11 août 2019 à 20:50:37

Super merci des conseils, mais je vais essayer de m'en sortir avec ma methode de depart, je veux pas abandonner maintenant !

Pour inverser les valeurs j'ai pas trouvé mieux que ca

if xMin1 > xMin2:
    xMin1 = xMin1 + xMin2
    xMin2 = xMin1 - xMin2
    xMin1 = xMin1 - xMin2
    xMax1 = xMax1 + xMax2
    xMax2 = xMax1 - xMax2
    xMax1 = xMax1 - xMax2
    yMin1 = yMin1 + yMin2
    yMin2 = yMin1 - yMin2
    yMin1 = yMin1 - yMin2
    yMax1 = yMax1 + yMax2
    yMax2 = yMax1 - yMax2
    yMax1 = yMax1 - yMax2

Tu n'as pas besoin, d'ailleurs, il serait plus approprié d'utiliser les fonctions min ou max de Python (comme on te l'a suggéré).

Si on prend mal l'exo, on peut se noyer dans de multiples cas. En particulier raisonner sur des maximums ou minimums n'est pas forcément utile.

Tout revient à traduire la chose suivante : on dispose de 4 entiers a, b, c, et d tels que 

a<=b et c<=d (c'est l'énoncé qui le suppose)

et on doit trouver une condition pour que les segments [a, b) et [c,d) aient au moins un point commun (faire un dessin peut aider ). En réalité, il est beaucoup plus simple (me semble-t-il) de répondre à la question de quand les deux segments n'ont pas d'intersection (*). Et de même pour l'exercice, il est plus simple de répondre quand les deux rectangles NE s'intersectent PAS.

(*) quand l'un est complètement à gauche de l'autre.

C'est un très bon exercice.

Par ailleurs, une solution à base d'intersection de set ne marchera pas (dépassement du temps limite).

-
Edité par PascalOrtiz 12 août 2019 à 1:14:09

Bonjour, je suis bloqué au même niveau.

Mon code réussis 2 test et rate le reste. Si vous avez des conseils à me donner je suis preneur
Voici le code :

nbPaires = int(input())
for loop in range(nbPaires):
   xMin1 = int(input())
   xMax1 = int(input())
   yMin1 = int(input())
   yMax1 = int(input())
   xMin2 = int(input())
   xMax2 = int(input())
   yMin2 = int(input())
   yMax2 = int(input())
if (((xMax1 > xMin2) and (yMax1 > yMin2))) and (((xMin1 < xMin2) and (yMin1 < yMin2))):
        print("OUI")

elif (((xMax2 > xMin1) and (yMax2 > yMin1))) and(((xMin2 < xMin1) and (yMin2 < yMin1))):
        print("OUI")
        
elif (((xMax1 > xMin2) and (yMin1 < yMax2))) and (((xMin1 < xMin2) and (yMax1 > yMax2))):
        print("OUI")
        
elif (((xMax2 > xMin1) and (yMin2 < yMax1)) and ((xMin2 < xMin1) and (yMax2 > yMax1))):
        print("OUI")

else:
    print("NON")

Mon conseil reste le même qu'il y a deux ans :

Dan737 a écrit:

Voici la clé du succès. Il suffit de se rendre compte que si R1.left > R2.right, alors peu importe l'ordonnée de l'un ou de l'autre, il ne pourront jamais avoir d'intersection. Je peux recommencer le raisonnement pour R1.right < R2.left et à nouveau, il n'y aura jamais d'intersection. Tu auras compris que ça s'applique aussi à R1.top < R2.bottom et R1.bottom > R2.top.

Si n'importe laquelle de ces 4 précédentes conditions n'est pas satisfaite, alors il y a forcément collision.

-
Edité par Dan737 3 septembre 2019 à 15:29:34

Merci Dan !

J'ai du mal à visualiser, en fait top et bottom sont les lignes du haut et du bas d'un rectangle et left et right sont les ligne gauche et droite de celui ci ? 

Dan737 a écrit:

Mon conseil reste le même qu'il y a deux ans :

Dan737 a écrit:

Voici la clé du succès. Il suffit de se rendre compte que si R1.left > R2.right, alors peu importe l'ordonnée de l'un ou de l'autre, il ne pourront jamais avoir d'intersection. Je peux recommencer le raisonnement pour R1.right < R2.left et à nouveau, il n'y aura jamais d'intersection. Tu auras compris que ça s'applique aussi à R1.top < R2.bottom et R1.bottom > R2.top.

Si n'importe laquelle de ces 4 précédentes conditions n'est pas satisfaite, alors il y a forcément collision.

Donc tu devrais avoir 4 if avec un print("NON") et à la fin un else avec un print("OUI").

-
Edité par Dan737 il y a moins de 30s

Oui c'est ça. Ce ne sont que des noms dans mon exemple. Toi tu les as appelés xMax, yMax et xMin, yMin.

Pour prendre la première condition R1.left > R2.right ça se lit : si le bord gauche du premier rectangle est plus grand (à droite) du bord droit du deuxième rectangle, alors il est impossible qu'il y ait une collision. Tu peux te prendre deux objets rectangulaire. Tu appelles l'un R1 et l'autre R2. Tu places le bord gauche de R1 à droite du bord droit de R2 et tu bouges le rectangle comme bon te semble, ils ne se toucheront jamais. 

-
Edité par Dan737 3 septembre 2019 à 15:43:16

Bonjour Dan737,

Tu m'es définitivement d'une aide précieuse j'ai appliqué ce que tu écrivais dans ton message du 18/11/2017 à 14h56 (et ai même réalisé un dessin afin d'illustrer et de mieux comprendre tes propos) ainsi que celui du 03/09/2019 en réponse à JulienFrancois1 toutefois le programme n'aboutit pas comme je le souhaiterais, saurais tu m'expliquer ce qui cloche dans mon code 1 ainsi que dans mon code 2 ?  

Code 1 :

nbPaires = int(input())
for loop in range(nbPaires):
   xMin1 = int(input())
   xMax1 = int(input())
   yMin1 = int(input())
   yMax1 = int(input())
   xMin2 = int(input())
   xMax2 = int(input())
   yMin2 = int(input())
   yMax2 = int(input())
if xMin1 > xMax2:
   print("NON")
if xMax1 < xMin2:
   print("NON")
if yMax1 < yMin2:
   print("NON")
if yMin1 > yMax2:
   print("NON")
else:
   print("OUI")

Code 2 :

nbPaires = int(input())
for loop in range(nbPaires):
   xMin1 = int(input())
   xMax1 = int(input())
   yMin1 = int(input())
   yMax1 = int(input())
   xMin2 = int(input())
   xMax2 = int(input())
   yMin2 = int(input())
   yMax2 = int(input())
   if xMin1 > xMax2:
      print("NON")
   if xMax1 < xMin2:
      print("NON")
   if yMax1 < yMin2:
      print("NON")
   if yMin1 > yMax2:
      print("NON")
   else:
      print("OUI")

Merci beaucoup =)

Bonne journée

Bonjour Dan, bonjour Clara  !

Après avoir vu tes explications Dan, j'ai essayer de me pencher sur un code qui correspondait à tes explications. Il me semble Clara qu'il ressemble au tient.
Quelque chose ne fonctionne pas dedans non plus, et je ne sais pas où :/

nbPaire= int(input())

for loop in range (nbPaire) : 
   recUnLeft = int(input())
   recUnRight = int(input())
   recUnTop = int(input())
   recUnBottom = int(input())
   recDeLeft = int(input())
   recDeRight= int(input())
   recDeTop = int(input())
   recDeBottom = int(input())
   
   if recUnLeft > recDeRight   :
   
      print("NON")
      
   elif recUnTop < recDeBottom :
      print("NON")
   
   elif  recUnRight < recDeLeft :
   
      print("NON")
      
   elif  recUnBottom > recDeTop :
      print("NON")
   
   else : 
      print("OUI")

Utilise des elif si tu ne veux pas que le else ne s'applique qu'à la dernière clause if.

Aussi dans ton code 1 les conditions étant en dehors de la boucle tu ne pourrais traiter que le dernier cas.

Bonjour Entwanne,

je me suis permis d'essayé le code 2 de Clara avec ton conseil. Il fonctionne mieux mais des erreurs persistent.
Manque-t-il des données ?

entwanne a écrit:

Utilise des elif si tu ne veux pas que le else ne s'applique qu'à la dernière clause if.

Aussi dans ton code 1 les conditions étant en dehors de la boucle tu ne pourrais traiter que le dernier cas.

Salut,

Pour pouvoir vous aider, il faut nous fournir les données entrées, le résultat attendu et le résultat du programme. Sans ça, à moins d'avoir recours une fois de plus à la boule de cristal, ça va être difficile d'avancer. Aussi tu dis avoir utiliser le code 2 de Clara avec les conseils d'Entwanne. Mais pourrais-tu poster ton nouveau code car on ne sait pas ce que tu as écrit.

Dan737 a écrit:

Salut,

Pour pouvoir vous aider, il faut nous fournir les données entrées, le résultat attendu et le résultat du programme. Sans ça, à moins d'avoir recours une fois de plus à la boule de cristal, ça va être difficile d'avancer. Aussi tu dis avoir utiliser le code 2 de Clara avec les conseils d'Entwanne. Mais pourrais-tu poster ton nouveau code car on ne sait pas ce que tu as écrit.

Dan,

J'ai tout regroupé, j'espère que ça pourra aider.

Voici le résultat attendu dans la consigne avec un exemple d'entrée et de sortie réalisé par le site :

Puis le code repris de Clara avec le conseil d'Entwanne de mettre des Elif :

nbPaires = int(input())
for loop in range(nbPaires):
   xMin1 = int(input())
   xMax1 = int(input())
   yMin1 = int(input())
   yMax1 = int(input())
   xMin2 = int(input())
   xMax2 = int(input())
   yMin2 = int(input())
   yMax2 = int(input())
   if xMin1 > xMax2:
      print("NON")
   elif xMax1 < xMin2:
      print("NON")
   elif yMax1 < yMin2:
      print("NON")
   elif yMin1 > yMax2:
      print("NON")
   else:
      print("OUI")

Puis le résultat obtenu pour ce code :

Si il manque quelque chose n'hésite pas

Peut-être une histoire de rectangles qui se frôlent qui sont considérés comme ayant une intersection par ton code.